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

时间：2021-11-23 13:06:02

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

}

相关文章