树上游戏

发表于 | 更新于 | 评论数：

此题显然有O（n）做法，喵喵喵？

解法：

让我们考虑一种颜色对答案的贡献

我们考虑把树中这种颜色的点都删掉，那么就会有很多的小树，这些小树中的点互相之间不会产生贡献，而不同树的两个点之间会产生贡献。

由此，我们可以得到每一种颜色，点的sum值就是 n - 所在小树的size。

由此，一个点的sum就是 n * 颜色数 - 每种颜色节点时所在小树的size。

我们考虑对于一棵小树的size，存在深度最小的节点上，那么后面就可以用树上差分实现覆盖。

求size，在回溯时遇到与当前颜色相同的点，就把整一颗子树的节点都删掉，那么一个点的答案就是， 子树的size - （当前删的个数 - 遍历时删的个数）。

因为每个节点只有一个颜色，所以一个节点会记录一次答案，特别的根节点的父亲设为所有颜色都有，全部统计一下。然后就树上差分传递下去，统计答案。

具体看代码吧。。。喵喵汪!!!(奇丑无比)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
long long read()
{
	char ch=getchar();long long x=0,ff=1;
	while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*ff;
}
void write(long long aa)
{
	if(aa<0) putchar('-'),aa=-aa;
	if(aa>9) write(aa/10);
	putchar('0'+aa%10);
	return;
}
long long n,sum,qwq;
long long vis[100005],ans[100005];
long long tot,head[100005],nx[200005],to[200005];
long long col[100005],sz[100005],jian[100005]；
long long lz[100005],bj[100005];
void jia(long long aa,long long bb)
{
	tot++;
	nx[tot]=head[aa];
	to[tot]=bb;
	head[aa]=tot;
	return;
}
void dfs(long long rt,long long fa)
{
	sz[rt]=1;
	long long tmp=jian[col[fa]];//遍历时删的个数
	for(long long i=head[rt];i;i=nx[i])
	{
		long long yy=to[i];
		if(yy==fa) continue;
		dfs(yy,rt);
		sz[rt]+=sz[yy];
	}
	jian[col[rt]]++;//删点
	if(fa)
	{
		lz[rt]=sz[rt]-jian[col[fa]]+tmp;//子树的size - （当前删的个数 - 遍历时删的个数）
		jian[col[fa]]+=lz[rt];//删点
	}
}
void getans(long long rt,long long fa)
{
	long long yuanbj=bj[col[fa]];
	qwq+=lz[rt]-bj[col[fa]];//差分啦
	bj[col[fa]]=lz[rt];
	ans[rt]=n*sum-qwq+bj[col[rt]];//自己颜色的显然是不能删掉的
	for(long long i=head[rt];i;i=nx[i])
	{
		long long yy=to[i];
		if(yy==fa) continue;
		getans(yy,rt);
	}
	bj[col[fa]]=yuanbj;
	qwq-=lz[rt]-bj[col[fa]];//还原啦
	return;
}
int main()
{
	n=read();
	for(long long i=1;i<=n;++i) 
	{
		col[i]=read();//col[i]<=100000,可能大于n。。。。
		if(!vis[col[i]]) vis[col[i]]=1,sum++;//sum颜色种类
	}
	for(long long i=1;i<n;++i) 
	{
		long long x=read(),y=read();
		jia(x,y);jia(y,x);
	}
	dfs(1,0);
	for(long long i=1;i<=100000;++i) if(vis[i]) qwq+=n-jian[i],bj[i]=n-jian[i];//特别处理根节点
	getans(1,0);
	for(long long i=1;i<=n;++i) write(ans[i]),puts("");
	return 0;
}

大家见谅，讲得自己都qwq了。。。