Description：

给一棵树，每条边的边权为 $0$ 或 $1$ ，询问有多少条合法的简单路径满足存在一个点（不是端点）左右 $0$ 边和 $1$ 边个数相同。

$1\leqslant n\leqslant 10^5$

Solution：

肯定是点分治，考虑经过某个点的路径的贡献，发现中间那个点一定在某边或者就是这个点，那么可以分别统计 $p[0/1][dep]$ 表示 $dep$ 深，是否存在一个点从根到这个点的值等于从根到最终点的值，这个可以在 $DFS$ 的同时维护一个桶来记录，用一般点分治子树容斥的思想很不好做，不如直接更暴力的枚举所有子树，然后依次统计子树之间的答案，也就是再设 $f[0/1][dep]$ 表示前几个子树 $dep$ 这个值的有这么多个然后统计就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	if(c == 0)c = -1;

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return;

}

int siz[MAXN],s,root = 0,d[MAXN];

#define INF 0x3f3f3f3f

bool vis[MAXN];

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		getroot(e[i].to,k);

		siz[k] += siz[e[i].to];

		d[k] = max(d[k],siz[e[i].to]);

	}

	d[k] = max(d[k],s - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

int t[MAXN];

map<int,int> p[2];

map<int,int> f[2];

map<int,int> cnt;

void dfs(int k,int fa,int val)

{//cout << k << " ";

	if(fa != 0)

	{

		t[++t[0]] = val;

		if(cnt[val] > 0)++p[1][val];

		else ++p[0][val];

		++cnt[val];

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		dfs(e[i].to,k,val + e[i].v);

	}

	if(fa != 0)--cnt[val];

	return;

}

long long calc(int k)

{//cout << k << " : " << endl;

	long long res = 0;

	f[0].clear();f[1].clear();

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		p[0].clear();p[1].clear();

		t[0] = 0;

		dfs(e[i].to,k,e[i].v);//cout << endl;

		sort(t + 1,t + 1 + t[0]);

		t[0] = unique(t + 1,t + 1 + t[0]) - t - 1;

		for(int x = 1;x <= t[0];++x)

		{

			//cout << t[x] << " " << p[0][t[x]] << " " << p[1][t[x]] << endl;

			res += 1ll * f[1][-t[x]] * p[1][t[x]];

			res += 1ll * f[1][-t[x]] * p[0][t[x]];

			res += 1ll * f[0][-t[x]] * p[1][t[x]];

		}

		res += 1ll * f[0][0] * p[0][0] + p[1][0];

		for(int x = 1;x <= t[0];++x)

		{

			f[1][t[x]] += p[1][t[x]];

			f[0][t[x]] += p[0][t[x]];

		}//cout << endl;

	}//cout << k << " " << res << endl;

	return res;

}

long long ans = 0;

void divide(int k)

{

	vis[k] = true;

	ans += calc(k);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		s = siz[e[i].to];root = 0;

		getroot(e[i].to,0);

		divide(root);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	int a,b,c;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	s = n;root = 0;d[0] = INF;

	getroot(1,0);

	divide(root);

	cout << ans << endl;

	return 0;

}