Description：

给一棵树，每个点有颜色，求以每个点为根的子树出现次数最多的颜色的编号和。

$1\leqslant n\leqslant10^5$

Solution：

通过这题学习一下树上启发式合并。

树上启发式合并实际上是一个静态的链分治，把每个节点的贡献分成两类，一是对计算这个点的答案的贡献，二是对当前计算的这个点的贡献，对整棵树进行轻重链剖分后，对于当前这个点，先 $dfs$ 所有轻子树，计算出来了所有轻子树的答案，但是不保留它对当前这个点的贡献，然后 $dfs$ 重儿子，计算所有重儿子的贡献，保留它对当前这个点的贡献，然后再 $dfs$ 轻子树，计算他对当前这个点的贡献，这样每个重儿子只 $dfs$ 了一遍，优化了时间复杂度。

这道题的话，对轻子树不保留它的出现次数，对重儿子保留，就可以计算答案了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int col[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

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

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

	return;

}

int son[MAXN],siz[MAXN];

void dfs(int k,int fa)

{

	siz[k] = 1;

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

	{

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

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

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

		if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

		{

			son[k] = e[i].to;

		}

	}

	return;

}

long long ans[MAXN];

int cnt[MAXN];

bool isheavy[MAXN];

int maxv = 0;

pair<int,long long> f[MAXN];

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

{

	int &c = cnt[col[k]];

	f[c].first--;f[c].second -= col[k];

	c += val;

	f[c].first++;f[c].second += col[k];

	if(val == 1)maxv = max(maxv,c);

	else if(f[maxv].first == 0)--maxv;

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

		if(e[i].to != fa && !isheavy[e[i].to])updata(e[i].to,k,val);

	return;

}

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

{

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

		if(e[i].to != fa && e[i].to != son[k])dfs(e[i].to,k,0);

	if(son[k] != 0){dfs(son[k],k,1);isheavy[son[k]] = true;}

	updata(k,fa,1);

	ans[k] = f[maxv].second;

	isheavy[son[k]] = false;

	if(!keep)updata(k,fa,-1);

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&col[i]);

	int a,b;

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

	{

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

		add(a,b);

	}

	dfs(1,0);

	dfs(1,0,1);

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

	{

		printf("%I64d ",ans[i]);

	}

	puts("");

	return 0;

}