【BZOJ3697】采药人的路径
Description
采药人的药田是一个树状结构，每条路径上都种植着同种药材。
采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。
Input
第1行包含一个整数N。
接下来N-1行，每行包含三个整数a_i、b_i和t_i，表示这条路上药材的类型。
Output
输出符合采药人要求的路径数目。
Sample Input
7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1
Sample Output
1
HINT
对于100%的数据，N ≤ 100,000。
题解：可能我以前学的是假的点分治~
注意一点：起点和终点相同，休息点不同的路径，算作相同的路径。
当我们以x为分治中心时，我们遍历x的所有子树，并令f[i][0/1]表示在之前扫过的子树中，到x的路径上的阳-阴=i，不存在（存在）一个休息点的点数，g[i][0/1]表示在当前的子树中，到x的路径上的阳-阴=i，不存在（存在）一个休息站的点数。那么用f和g来更新答案就行了。别忘了算上起点为x的情况。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=100010;
typedef long long ll;
int n,cnt,root,mx,maxx,tot,d;
ll ans;
int to[maxn<<1],next[maxn<<1],val[maxn<<1],head[maxn],dep[maxn],siz[maxn],vis[maxn],s[maxn];
int f[maxn<<1][2],g[maxn<<1][2];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void getr(int x,int fa)
{
siz[x]=1;
int mx=0;
for(int i=head[x];i!=-1;i=next[i])
{
if(vis[to[i]]||to[i]==fa) continue;
getr(to[i],x),siz[x]+=siz[to[i]],mx=max(mx,siz[to[i]]);
}
if(max(tot-siz[x],mx)<maxx) root=x,maxx=max(tot-siz[x],mx);
}
void getd(int x,int fa)
{
d=max(d,max(dep[x],-dep[x]));
if(s[dep[x]+maxn]) g[dep[x]+maxn][1]++;
else g[dep[x]+maxn][0]++;
s[dep[x]+maxn]++;
for(int i=head[x];i!=-1;i=next[i])
{
if(vis[to[i]]||to[i]==fa) continue;
dep[to[i]]=dep[x]+val[i],getd(to[i],x);
}
s[dep[x]+maxn]--;
}
void dfs(int x)
{
vis[x]=1;
int i,j,dd=0;
for(i=head[x];i!=-1;i=next[i])
{
if(vis[to[i]]) continue;
dep[to[i]]=val[i],d=0,getd(to[i],x),dd=max(dd,d);
for(j=maxn-d;j<=maxn+d;j++) ans+=(ll)f[2*maxn-j][0]*g[j][1]+f[2*maxn-j][1]*g[j][0]+f[2*maxn-j][1]*g[j][1];
ans+=(ll)f[maxn][0]*g[maxn][0]+g[maxn][1];
for(j=maxn-d;j<=maxn+d;j++) f[j][0]+=g[j][0],f[j][1]+=g[j][1],g[j][0]=g[j][1]=0;
}
for(i=maxn-dd;i<=maxn+dd;i++) f[i][0]=f[i][1]=0;
for(i=head[x];i!=-1;i=next[i])
{
if(vis[to[i]]) continue;
maxx=1<<30,tot=siz[to[i]],getr(to[i],x),dfs(root);
}
}
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
int main()
{
n=rd();
int i,a,b,c;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd(),b=rd(),c=rd()*2-1,add(a,b,c),add(b,a,c);
maxx=1<<30,tot=n,getr(1,0),dfs(root);
printf("%lld",ans);
return 0;
}