[BZOJ3697] 采药人的路径

采药人的药田是一个树状结构，每条路径上都种植着同种药材。采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

如XHT大佬所说，这是点分治裸题一个。

点分治，则问题就变成求过根满足条件的路径数。

路径上的休息站一定是在起点到根的路径上，或者根到终点的路径上。

如何判断一条从根出发的路径是否包含休息站？只要在dfs中记录下这条路径的和x，同时用个标志数组判断这条路径是否存在前缀和为x的节点。

枚举根节点的每个子树。用f[i][0/1]，g[i][0/1]分别表示前面几个子树以及当前子树和为i的路径数目，0和1用于区分路径上是否存在前缀和为i的节点。那么当前子树的贡献就是

其中d为当前子树的深度。然后再加上

（当前根作为休息点/当前根作为端点的情况）

这样复杂度就为 n log n。

为啥要写博客？调题太痛苦了，这题调了3小时，在XHT帮助下知道是数组开小了，要记录下来，以后少出错。

// Author : WangZhikun
// Date   : 2018.07.31
#include <cstdio>
#include <vector>
#include <iostream>
#define PII pair<ll,ll>
#define MP make_pair
#define PB push_back
#define FF first
#define SS second
#define N 110000
using namespace std;
typedef long long ll;

ll n,u,v,w,rt,ctsz,ans;
ll kgb[200020] = {0},sz[200020] = {0},ccv[200020] = {0},mx[200020],ddd[220010][2] = {0},kkk[220010][2],depth[200020],mdepth[200020];
vector<PII> G[200020];

void dfs1(ll num,ll fa){
	sz[num] = 1;mx[num]=0;
	for(ll i=0;i<G[num].size();i++){
		ll ct = G[num][i].FF;
		if(kgb[ct]||ct == fa)continue;
		dfs1(ct,num);
		sz[num]+=sz[ct];
		mx[num] = max(mx[num],sz[ct]);
	}
	mx[num] = max(mx[num],ctsz-sz[num]);
	if(mx[num]<mx[rt])rt = num;
}
void dfs2(ll num,ll fa,ll x){
	if(ccv[x]>0)ddd[x][1]+=1;
	else ddd[x][0]+=1;
	ccv[x]+=1;
	sz[num] = 1;
	for(PII ech:G[num]){
		ll ct = ech.FF;if(kgb[ct]||ct == fa)continue;
		dfs2(ct,num,x+ech.SS);
		sz[num]+=sz[ct];
	}
	ccv[x]-=1;
}
void dfs3(ll num,ll fa){
	mdepth[num] = depth[num];
	sz[num] = 1;
	for(PII ech:G[num]){
		ll ct = ech.FF;if(kgb[ct]||ct == fa)continue;
		depth[ct] = depth[num]+1;
		dfs3(ct,num);
		sz[num]+=sz[ct];
		mdepth[num] = max(mdepth[num],mdepth[ct]);
	}
}
void solve(ll num){
	rt = 100005;mx[rt] = 10000005;
	dfs1(num,-1);
	depth[rt] = 0;
	dfs3(rt,-1);
	kgb[rt] = 1;
	for(ll i = N-mdepth[rt];i<=N+mdepth[rt];i++)kkk[i][0] = kkk[i][1] = 0;
	for(auto ech:G[rt]){
		ll ct = ech.FF;
		if(kgb[ct])continue;
		dfs2(ct,rt,N+ech.SS);
		ans+=ddd[N][0]*kkk[N][0];
		ans+=ddd[N][1];
		for(ll i = -mdepth[ct];i<=+mdepth[ct];i++){
			ans+=ddd[i+N][0]*kkk[-i+N][1]+ddd[i+N][1]*kkk[-i+N][0]+ddd[i+N][1]*kkk[N-i][1];
		}
		for(ll i = N-mdepth[ct];i<=N+mdepth[ct];i++){
			kkk[i][0]+=ddd[i][0];
			kkk[i][1]+=ddd[i][1];
			ddd[i][0] = ddd[i][1] = 0;
		}
	}
	for(auto ech:G[rt]){
		if(kgb[ech.FF])continue;
		if(sz[ech.FF]>=5){
			ctsz = sz[ech.FF];
			solve(ech.FF);
		}
	}
}
int main(){
	cin>>n;
	for(ll i=1;i<n;i++){
		cin>>u>>v>>w;
		if(!w)w=-1;
		G[u].PB(MP(v,w));
		G[v].PB(MP(u,w));
	}
	ctsz = n;solve(1);
	cout<<ans<<endl;;
	return 0;
}

[latex]