# CodeForces 600E.Lomsat gelral dsu on tree 树上启发式合并

## Example

```15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13```
`6 5 4 3 2 3 3 1 1 3 2 2 1 2 3`

## 题解

dsu实际上是并查集的问题，但这个算法并不是什么树上并查集，而是借鉴了并查集中启发式合并优化的思想，将这个思想运用到了树上。

## 代码

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int x,y;
typedef long long ll;
ll ans[maxn],c[maxn],sum,mx;
int son[maxn],siz[maxn],f[maxn],cnt[maxn];
vector<int>g[maxn];
int n,s;
void dfs(int now,int fa){
f[now] = fa;
siz[now] = 1;
for(auto it : g[now]){
if(it == fa)continue;
dfs(it,now);
siz[now] += siz[it];
if(siz[it] > siz[son[now]])
son[now] = it;
}
return;
}
void cal(int now,int fa,int d){
cnt[c[now]] += d;
if(cnt[c[now]] == mx){
sum += c[now];
}
else if(cnt[c[now]] > mx){
mx = cnt[c[now]];
sum = c[now];
}
for(auto it : g[now]){
if(it == fa || it == s)continue;
cal(it,now,d);
}
return;
}
void work(int now,int fa,int flag){
for(auto it : g[now]){
if(it != f[now] && it != son[now])
work(it,now,0);
}
if(son[now]){
work(son[now],now,1);
s = son[now];
}
cal(now,fa,1);
ans[now] = sum;
s = 0;
if(!flag){
cal(now,f[now],-1);
sum = 0;
mx = 0;
}
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1;i <= n;++i){
cin >> c[i];
g[i].clear();
son[i] = siz[i] = f[i] = ans[i] = 0;
}
for(int i = 1;i < n;++i){
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,1);
sum = mx = 0;
work(1,1,0);
cout << ans[1];
for(int i = 2;i <= n;++i){
cout << " " << ans[i];
}
cout << endl;
return 0;
}```