【bzoj3697】采药人的路径

【bzoj3697】采药人的路径
题意：
有每条边有一种属性（阴/阳）求有多少条路径阴=阳，且能找到一个休息点使得起点到休息点，休息点到终点阴阳平衡.
分析：
本题中边权为0/1代表阴阳，不妨将0转化成-1，这样若一条路径阴阳平衡，那么其路径长度即为0.
点分治。
那么要解决的问题就是如何计算经过当前根节点有多少合法路径。
一个一个子树处理
处理当前子树时，对于当前子树中的一个点，其到根的路径长度为x，则之前的子树中的路径长度需要是-x,才满足第一个条件。如何判断是否有休息点呢。
假设当前根为root，之前子树中的一个点x,当前子树中的一个点y，dis表示到根的路径长。
则x-y的路径为x–root–y
长度为dis[x]+dis[y];
现已知dis[x]+dis[y]=0;
那么假设有一个休息点z(z!=y,z!=root)，在root–y的路径中
故dis[x]+dis[z]=0,dis[z]=-dis[x]=dis[y];
所以当存在dis[z]=dis[y] (z!=y,z!=root)是就有一个在root–y的路径中的休息点z了
x–root同理
设置两个数组g[i][0/1],f[i][0/1];
g[i][0]表示已近处理过的子树中的点中，其到根的路径长度为i，且其到根的路径上存在休息点的数量，g[i][1]则表示不存在休息点
f[i][0/1]表示的是当前子树中的点，其余定义与g相同
为避免重复计算，计算一颗子树贡献时分类讨论
ps:
根到根这条路径也记录在了g数组内，
所以对于两端点都不在根上，即根为休息点这种情况
贡献是：f[0][0]*(g[0][0]-1);
因为长度可能是负数，所以将下标平移？？

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,Link[100010],d[100010],Ma;
ll f[200010][2],g[200010][2],ans;
bool vis[100010];
int sum[100010],s,cnt[200020],dis[100010],Min,root,maxx,minn,t=0;
struct dsa
{
	int nex,v,w;
}e[200010];
void insert(int xx,int yy,int zz)
{
	e[++t].nex=Link[xx];
	e[t].v=yy;
	e[t].w=zz;
	Link[xx]=t;
}
void get_root(int now,int fa)
{
	sum[now]=1;int Max=0;
	for (int i=Link[now];i;i=e[i].nex)
	{
		if (e[i].v==fa||vis[e[i].v]) continue;
		get_root(e[i].v,now);
		sum[now]+=sum[e[i].v];
		Max=max(Max,sum[e[i].v]);
    }
    Max=max(Max,s-sum[now]);
    if (Max<Min) {Min=Max;root=now;}
}
void get_dis(int now,int fa)
{
	maxx=max(maxx,d[now]);
	if (cnt[dis[now]+n]) f[dis[now]+n][1]++;
	else f[dis[now]+n][0]++;
	cnt[dis[now]+n]++;
	for (int i=Link[now];i;i=e[i].nex)
	{
		if (e[i].v==fa||vis[e[i].v]) continue;
		dis[e[i].v]=dis[now]+e[i].w;
		d[e[i].v]=d[now]+1;
	    get_dis(e[i].v,now);
    }
    cnt[dis[now]+n]--; 
    return ;
}
void solve(int now)
{
	vis[now]=true;
	dis[now]=0;
	g[0+n][0]=1;
	Ma=0;
	for (int i=Link[now];i;i=e[i].nex)
	{
		maxx=0;
		if (vis[e[i].v]) continue;
		dis[e[i].v]=e[i].w;
		d[e[i].v]=1;
		get_dis(e[i].v,0);
		ans+=f[0+n][0]*(g[0+n][0]-1);
		Ma=max(Ma,maxx);
		for (int j=-maxx;j<=maxx;j++)
	 		ans+=g[n+j][0]*f[n-j][1]+g[n+j][1]*f[n-j][0]+g[n+j][1]*f[n-j][1];
	 	for (int j=-maxx;j<=maxx;j++)
	 	{
	 		g[n+j][0]+=f[n+j][0];
	 		g[n+j][1]+=f[n+j][1];
	 		f[n+j][0]=0;
	 		f[n+j][1]=0;
	    }
    }
    for (int i=-Ma;i<=Ma;i++)
      g[i+n][0]=g[i+n][1]=0;
	for (int i=Link[now];i;i=e[i].nex)
	{
		if (vis[e[i].v]) continue;
		Min=1e9;root=0;
		s=sum[e[i].v];
		get_root(e[i].v,0);
		solve(root);
    }
    return ;
}
int main()
{
	freopen("yinyang.in","r",stdin);
	freopen("yinyang.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<n;i++)
	{
		int xx,yy,zz;
		scanf("%d%d%d",&xx,&yy,&zz);
		if (zz==0) zz=-1;
		insert(xx,yy,zz);
		insert(yy,xx,zz);
    }
    s=n;
    Min=1e9;root=0;
    get_root(1,0);
    solve(root);
    printf("%lld",ans);
}