首页 > 代码库 > 【BZOJ3697】采药人的路径 点分治

【BZOJ3697】采药人的路径 点分治

2024-10-10 18:32:02   213人阅读

【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

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

 

【BZOJ3697】采药人的路径 点分治


联系
我们