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

统计路径？嗯往点分治上想。

把0和1转化为-1和1，求和完dis为0的路径就是阴阳平衡的路径了。

如果题目没有限制要有中间休息站那就是比较裸的点分治淀粉质题了。

用两个数组 f[dis]和g[dis]。

f[dis]：此时DFS的这棵子树里到根距离为dis的路径条数。

g[dis]：此时DFS的这棵子树外到根距离为dis的路径条数。

然后里外配对一下统计答案就可以啦~

如果有休息站也没复杂到哪里去。

f[dis][0/1]和g[dis][0/1]多加上一维，表示这条距离为dis的这些路径上是否到之前某个地方距离和为0。

（有点抽象画个图）

那这时中间的那个点就可以作为中间0点了上面dis的部分再和子树外的路径配对即可。

这样就可以完美统计出答案了。

代码~

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<cmath>
  7 
  8 #define For(i,a,b) for(register int i=a;i<=b;++i)
  9 #define Dwn(i,a,b) for(register int i=a;i>=b;--i)
 10 #define Re register
 11 #define Pn putchar('
')
 12 #define llg long long
 13 #define f(a,b) fx[a+100000][b]
 14 #define g(a,b) gx[a+100000][b]
 15 #define t(a) tx[a+100000]
 16 
 17 using namespace std;
 18 
 19 const int N=1e5+5;
 20 
 21 llg ans=0,fx[N*2][2],gx[N*2][2],tx[N*2];
 22 int head[N],nxt[N*2],v[N*2],w[N*2],siz[N],cnt=1;
 23 int tot,n,m,x,y,opt,vis[N],mx[N],rt;
 24 
 25 void read(int &v){
 26     v=0;
 27     char c=getchar();
 28     while(c<'0'||c>'9')c=getchar();
 29     while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar();
 30 }
 31 void add(int ux,int vx,int wx){
 32     cnt++;
 33     nxt[cnt]=head[ux]; head[ux]=cnt; v[cnt]=vx; w[cnt]=wx;
 34     cnt++;
 35     nxt[cnt]=head[vx]; head[vx]=cnt; v[cnt]=ux; w[cnt]=wx;
 36 }
 37 
 38 void dfsRT(int x,int fa){
 39     mx[x]=0; siz[x]=1;
 40     for(Re int i=head[x];i;i=nxt[i]){
 41         int vv=v[i]; 
 42         if(vv==fa||vis[vv])continue;
 43         dfsRT(vv,x); siz[x]+=siz[vv];
 44         if(siz[vv]>mx[x])mx[x]=siz[vv];
 45     }
 46     if(tot-siz[x]>mx[x])mx[x]=tot-siz[x];
 47     if(mx[x]<mx[rt])rt=x;
 48 }
 49 int getRT(int x,int fa,int sz){
 50     rt=0; mx[rt]=2147483600;
 51     tot=sz; dfsRT(x,fa); return rt;
 52 }
 53 
 54 int mxD;
 55 void dfsSV(int x,int dis,int fa){
 56     if(t(dis))f(dis,0)++;
 57     else f(dis,1)++;
 58     mxD=max(mxD,abs(dis));
 59     t(dis)++;
 60     for(Re int i=head[x];i;i=nxt[i]){
 61         int vv=v[i];if(vv==fa||vis[vv])continue;
 62         dfsSV(vv,dis+w[i],x);
 63     }
 64     t(dis)--;
 65 }
 66 void Solve(int x){
 67     vis[x]=1;
 68     int maxD=0; 
 69     for(Re int i=head[x];i;i=nxt[i]){
 70         int vv=v[i];
 71         if(vis[vv])continue;
 72         mxD=0;
 73         dfsSV(vv,w[i],x);
 74         maxD=max(mxD,maxD);  
 75         ans+=f(0,0);
 76         For(j,-mxD,mxD){
 77             if(j==0)ans+=f(j,1)*g(j,1);
 78             ans+=f(j,0)*g(-j,0);
 79             ans+=f(j,0)*g(-j,1);
 80             ans+=f(j,1)*g(-j,0);
 81         } 
 82         For(j,-mxD,mxD){
 83             g(j,0)+=f(j,0);
 84             g(j,1)+=f(j,1);
 85             f(j,0)=f(j,1)=0;
 86         }
 87     }
 88     For(j,-maxD,maxD)g(j,0)=g(j,1)=0;
 89     for(Re int i=head[x];i;i=nxt[i]){
 90         int vv=v[i]; if(vis[vv])continue;
 91         int Nrt=getRT(vv,x,siz[vv]);
 92         Solve(Nrt);
 93     }
 94 }
 95             
 96 int main(){ 
 97     read(n);
 98     For(i,1,n-1){
 99         read(x); read(y); read(opt);
100         if(!opt)opt=-1;
101         add(x,y,opt);
102     }
103     int Wrt=getRT(1,0,n); 
104     Solve(Wrt);
105     cout<<ans<<endl;
106     return 0;
107 }