P4930 「FJ2014集训」采药人的路径

题目描述

采药人的药田是一个树状结构，每条路径上都种植着同种药材。
采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

输入输出格式

输入格式：

第1行包含一个整数N。
接下来N-1行，每行包含三个整数a_i、b_i和t_i，表示这条路上药材的类型。

输出格式：

输出符合采药人要求的路径数目。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

对于100%的数据，N ≤ 100,000。

sol：点分治（板子题），把0看成-1，没有条件2的限制就是求和是0的路径条数，用dp[i]表示和为i的方案数，有了2的限制就要多一维记录当前这条路径是否可以有断点，断点就是记录当前的dis前面是否出现过，即是否当前路径有一段后缀为0

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

  ll s=; bool f=; char ch=' ';

  while(!isdigit(ch)) {f|=(ch=='-'); ch=getchar();}

  while(isdigit(ch)) {s=(s<<)+(s<<)+(ch^); ch=getchar();}

  return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

  if(x<) {putchar('-'); x=-x;}

  if(x<) {putchar(x+''); return;}

  write(x/); putchar((x%)+'');

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int N=,M=,inf=0x3f3f3f3f;

int n;

ll ans=;

int tot=,Next[M],to[M],val[M],head[N];

int rt,Sum,mx[N],sz[N];

int dis[N],dep[N],mxdep,arrdis[M];

bool Vis[N];

int dp[][][M];

inline void Link(int x,int y,int z)

{

  Next[++tot]=head[x]; to[tot]=y; val[tot]=z; head[x]=tot;

}

inline void getrt(int x,int fat)

{

  int e;

  sz[x]=; mx[x]=;

  for(e=head[x];e;e=Next[e]) if((to[e]!=fat)&&(!Vis[to[e]]))

  {

    getrt(to[e],x); sz[x]+=sz[to[e]]; mx[x]=max(mx[x],sz[to[e]]);

  }

  mx[x]=max(mx[x],Sum-sz[x]);  if(mx[x]<mx[rt]) rt=x;

}

inline void calc(int x,int fat,int o)

{

  int e;

  mxdep=max(mxdep,dep[x]);

  if(arrdis[dis[x]+n]) dp[o][][dis[x]+n]++;

  else dp[o][][dis[x]+n]++;

  arrdis[dis[x]+n]++;

  for(e=head[x];e;e=Next[e]) if((!Vis[to[e]])&&(to[e]!=fat))

  {

    dep[to[e]]=dep[x]+; dis[to[e]]=dis[x]+val[e]; calc(to[e],x,o);

  }

  arrdis[dis[x]+n]--;

}

inline void dfs(int x)

{

  int e,i,mm=;

  Vis[x]=; dp[][][n]=;

  for(e=head[x];e;e=Next[e]) if(!Vis[to[e]])

  {

    dis[to[e]]=val[e]; dep[to[e]]=;

        mxdep=;

    calc(to[e],x,);

        mm=max(mm,mxdep);

    ans=ans+(dp[][][n]-)*dp[][][n];

    for(i=-mxdep;i<=mxdep;i++)

    {

      ans=ans+dp[][][n+i]*dp[][][n-i]+dp[][][n+i]*dp[][][n-i]+dp[][][n+i]*dp[][][n-i];

    }

    for(i=n-mxdep;i<=n+mxdep;i++)

    {

      dp[][][i]+=dp[][][i];

      dp[][][i]+=dp[][][i];

      dp[][][i]=dp[][][i]=;

    }

  }

  // puts("#####################################");

  for(i=n-mm;i<=n+mm;i++) dp[][][i]=dp[][][i]=;

  for(e=head[x];e;e=Next[e]) if(!Vis[to[e]])

  {

    Sum=sz[to[e]]; mx[rt=]=inf; getrt(to[e],x); dfs(rt);

  }

}

int main()

{

  int i,x,y,z;

  R(n);

  for(i=;i<n;i++)

  {

    R(x); R(y); R(z); if(z==) z=-;

    Link(x,y,z); Link(y,x,z);

  }

  Sum=n; mx[rt=]=inf;

  getrt(,);

  // cout<<"rt="<<rt<<endl;

  dfs(rt);

  Wl(ans);

  return ;

}

巴特西

luogu4930

P4930 「FJ2014集训」采药人的路径

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章