BZOJ 3697: 采药人的路径

###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。

###Solution
点分治，边权为0变成-1，dfs时记前缀和，休息站就判之前有没有出现过该权值，注意处理根节点

###Code
```c++
#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))

int n,p[100001],em=1,sz[100001],ro,nro,apr[200000],cnt[200000][2];
ll ans;
bool vis[100001];

struct edge
{
	int to,ne,w;
}e[200000];

inline void add(int a,int b,int w)
{
	e[em].to=b,e[em].ne=p[a],e[em].w=w,p[a]=em++;
}

void dfs1(int x,int fa)
{
	sz[x]=1;
	for(int i=p[x];i;i=e[i].ne)
		if(!vis[e[i].to]&&e[i].to!=fa)
			dfs1(e[i].to,x),sz[x]+=sz[e[i].to];
}

void dfs2(int x,int fa)
{
	bool ok=sz[ro]<=2*sz[x];
	for(int i=p[x];i;i=e[i].ne)
		if(!vis[e[i].to]&&e[i].to!=fa)
		{
			dfs2(e[i].to,x);
			if(sz[e[i].to]*2>sz[ro])ok=0;
		}
	if(ok)nro=x;
}

void dfs3(int x,int fa,int len)
{
	if(len)
	{
		if(apr[len+n])
			ans+=cnt[n-len][0];
		else
			ans+=cnt[n-len][1];
	}
	else
	{
		if(apr[len+n])
			ans+=cnt[n][0]+1;
		else
			ans+=cnt[n][0];
	}
	apr[len+n]++;
	for(int i=p[x];i;i=e[i].ne)
		if(!vis[e[i].to]&&e[i].to!=fa)
			dfs3(e[i].to,x,len+e[i].w);
	apr[len+n]--;
}

void dfs4(int x,int fa,int len)
{
	if(len)
	{
		if(apr[len+n])
			cnt[n+len][0]++,cnt[n+len][1]++;
		else
			cnt[n+len][0]++;
	}
	else
	{
		cnt[n][0]++;
	}
	apr[len+n]++;
	for(int i=p[x];i;i=e[i].ne)
		if(!vis[e[i].to]&&e[i].to!=fa)
			dfs4(e[i].to,x,len+e[i].w);
	apr[len+n]--;
}

void dfs5(int x,int fa,int len)
{
	cnt[n+len][0]=cnt[n+len][1]=0;
	for(int i=p[x];i;i=e[i].ne)
		if(!vis[e[i].to]&&e[i].to!=fa)
			dfs5(e[i].to,x,len+e[i].w);
}

void solve(int x)
{
	dfs1(x,0);
	ro=x;
	dfs2(x,0);
	vis[nro]=1;
	for(int i=p[nro];i;i=e[i].ne)
		if(!vis[e[i].to])dfs3(e[i].to,0,e[i].w),dfs4(e[i].to,0,e[i].w);
	dfs5(nro,0,0);
	for(int i=p[nro];i;i=e[i].ne)
		if(!vis[e[i].to])solve(e[i].to);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c?c:-1),add(b,a,c?c:-1);
	}
	solve(1);
	printf("%lld\n",ans);
}
```

BZOJ 3697: 采药人的路径

最新文章

最近回复

分类

归档

其它