meepo's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

Source

    我的第四道点分。。也是最近点分收尾题。。

    看题解前没有思路。。还以为每一个重心就是休息点。。。发现自己真是傻到家了。。

    因为这道题出现在同一颗子树中的情况很难处理。。所以可以让当前的子树和已经处理完的子树合并。。

然后我们可以把阴性路径的权值赋为-1，阳性的赋为1，这样求一下两点之间的路径和就可以知道中间的阴阳点的多少了。。。用\(g[i][0..1]\)和\(f[i][0..1]\)分别表示之前的子树和当前子树中权值和为i的点的数量。。0，1分别表示这条路径上有没有休息点。。然后进行合并\(ans+=g[i][1]*f[-i][1]+g[i][0]*f[-i][1]+g[i][1]*f[-i][0]\)。。还要注意如果两边的路径和为0但是没有休息点。。可以把重心作为休息点。。

   判断一条路径上有没有休息点的方法是在他到根的路径上找是否有权值和等于他的点。。如果有。。那个店就是休息点。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
struct data{int x,y,s,next;} e[N<<1];
int t[N<<1],dis[N],vis[N],deep[N],son[N],F[N],x,y,s,n,root,cnt,head[N],sum,mxdeep;
long long ans,f[N<<1][2],g[N<<1][2];
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9'){if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
void Insert(int x,int y,int s){
	e[++cnt].x = x;e[cnt].y = y;e[cnt].s = s;
	e[cnt].next = head[x];head[x] = cnt;
}
void getroot(int x,int fa){
	son[x] = 1;F[x] = 0;
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y] && e[i].y!=fa){
			getroot(e[i].y,x);
			son[x]+=son[e[i].y];
			F[x] = max(F[x],son[e[i].y]);
		}
	F[x] = max(F[x],sum-F[x]);
	if (F[x]<F[root]) root = x;
}
void getdeep(int x,int fa){
	mxdeep = max(mxdeep,deep[x]);
	if (t[dis[x]]) f[dis[x]][1]++;
	else f[dis[x]][0]++;
	t[dis[x]]++;
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y] && e[i].y!=fa){
			dis[e[i].y] = dis[x]+e[i].s;
			deep[e[i].y] = deep[x]+1;
			getdeep(e[i].y,x);
		}
	t[dis[x]]--;
}
void work(int x){
	int mx = 0;vis[x] = 1;g[n][0] = 1;
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y]){
			dis[e[i].y] = n+e[i].s;
			deep[e[i].y] = 1;
			mxdeep = 1;getdeep(e[i].y,x);mx = max(mx,mxdeep);
			ans+=(g[n][0]-1)*f[n][0];
			for (int j=-mxdeep;j<=mxdeep;j++)
				ans+=g[n+j][1]*f[n-j][1]+g[n+j][1]*f[n-j][0]+g[n+j][0]*f[n-j][1];
			for (int j=n-mxdeep;j<=n+mxdeep;j++){
				g[j][0]+=f[j][0];g[j][1]+=f[j][1];
				f[j][1] = f[j][0] = 0;				
			}
		}
	for (int i=n-mx;i<=n+mx;i++) g[i][0] = g[i][1] = 0;
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y]){
			sum = son[e[i].y];
			root = 0;
			getroot(e[i].y,-1);
			work(root);
		}
}
int main(){
	n = read();
	for (int i=1;i<n;i++){
		x = read();y = read();s = read();
		if (s) Insert(x,y,1),Insert(y,x,1);
		else Insert(x,y,-1),Insert(y,x,-1);
	}
	sum = n;F[0] = 1e9;
	getroot(1,-1);
	work(root);
	printf("%lld",ans);
}