考虑一个问题：我们如何维护一颗子树里面有多少个不同的颜色呢？
直观想法，如果可以离线，那我们可以通过dfs序把树上问题转换成为序列问题，从而将问题变成如何维护一段区间内有多少种不同的颜色。
也就是说，这个题用树上莫队可写。
但是回忆树上莫队的复杂度带了log有可能伤不起。
所以，我们采用玄学数据结构：树上启发式合并 Ｏ（nlogn）
这种数据结构多用于：１，无修改操作；２，只查询子树的答案。
算法基本思想：
运用到了树链剖分的思想，我们考虑轻重儿子。
我们先遍历一遍x结点轻儿子，同时维护轻儿子的各个结点的值。
在遍历一遍x结点重儿子；
最后在遍历一遍x结点轻儿子，将此次轻儿子所产生的影响和遍历重儿子所产生的影响合并。得到x的值。
树链处理代码：
void dfs1(int u, int fa) {
size[u] = 1;
for (int i = head[u]; i; i = tree[i].next) {
int v = tree[i].v;
if (v != fa) {
dfs1(v, u);
size[u] += size[v];
if (size[v] > size[son[u]]) son[u] = v;
}
}
}
下为求答案代码：
int dfs2(int u, int fa, bool keep, bool isson) {
int tmp = 0;
for (int i = head[u]; i; i = tree[i].next) {
int v = tree[i].v;
if (v != fa && v != son[u]) {
dfs2(v, u, 0, 0);
}
}
if (son[u]) tmp += dfs2(son[u], u, 1, 1);
for (int i = head[u]; i; i = tree[i].next) {
int v = tree[i].v;
if (v != fa && v != son[u]) {
tmp += dfs2(v, u, 1, 0);
}
}
if (!check[color[u]]) {
tmp++;
check[color[u]] = 1;
}
if (!keep || isson) ans[u] = tmp;
if (!keep) memset(check, 0, sizeof(check)), tmp = 0;
return tmp;
}
例题：https://codeforces.com/problemset/problem/600/E
本题属于无修改，查询子树，所以我们考虑树上启发式合并。
先遍历轻儿子，维护上面各个结点的值。
在遍历重儿子。最后重新遍历轻儿子。
#include"stdio.h"
#include"string.h"
#include"math.h"
#include"algorithm"
using namespace std;
typedef long long ll;
const int N = 200010;
int head[N],ver[N * 4],Next[N * 4],tot;
int n,c[N];
int d[N],Size[N],son[N],far[N];
ll ans[N];int Son;
int cnt[N];
int max_sum;ll sum;
void add(int x,int y)
{
ver[++ tot] = y; Next[tot] = head[x];
head[x] = tot;
}
void dfs1(int x,int fa)
{
Size[x] = 1; far[x] = fa;
d[x] = d[fa] + 1;
for(int i = head[x]; i; i = Next[i]){
int y = ver[i];
if(y == fa) continue;
dfs1(y,x);
Size[x] += Size[y];
if(son[x] == 0 || Size[son[x]] < Size[y]){
son[x] = y;
}
}
}
void add(int x,int fa,int val){
cnt[c[x]] += val;
if(cnt[c[x]] > max_sum){
max_sum = cnt[c[x]];
sum = c[x];
} else if(max_sum == cnt[c[x]]){
sum += c[x];
}
for(int i = head[x]; i; i = Next[i]){
int y = ver[i];
if(y == fa || y == Son) continue;
add(y,x,val);
}
}
void dfs2(int x,int fa,int op)
{
for(int i = head[x]; i; i = Next[i]){
int y = ver[i];
if(y == fa || y == son[x]) continue;
dfs2(y,x,0);
}
if(son[x]){
dfs2(son[x],x,1);
Son = son[x];
}
add(x,fa,1);///将其子树除重儿子外的结点所产生的影响进行添加维护。重儿子的影响已经在dfs中保存了下来
ans[x] = sum;
Son = 0;
if(op == 0){
add(x,fa,-1);///如果op==0 证明是轻儿子遍历过来的，所以在得到了当前结点的值之后，要把这次的操作影响进行删除
sum = 0; max_sum = 0;
}
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i ++)
scanf("%d",&c[i]);
for(int i = 1; i < n; i ++)
{
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs1(1,1);
dfs2(1,1,0);
for(int i = 1; i <= n; i ++)
if(i == 1) printf("%lld",ans[i]);
else printf(" %lld",ans[i]);
printf("
");
}