欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【bzoj3697】采药人的路径

程序员文章站 2022-05-08 18:06:00
...

【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);
}