题目链接：E. Lomsat gelral

最开始做这道题的时候，采用了dsu on tree的做法，其实这道题也可以用线段树合并来做。

就是用线段树动态维护区间的众数，然后更新答案即可。

但是要注意merge的时候，我们需要传入区间l，r，因为我们到端点的时候，值是一样的，所以直接更新，和pushup不一样。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=N*20;
int mx[M],lc[M],rc[M],res[M],n,c[N],cnt,ans[N],rt[N];
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
inline void push_up(int p){
	if(mx[lc[p]]>mx[rc[p]]){
		mx[p]=mx[lc[p]];	res[p]=res[lc[p]];
	}else if(mx[lc[p]]<mx[rc[p]]){
		mx[p]=mx[rc[p]];	res[p]=res[rc[p]];
	}else{
		mx[p]=mx[rc[p]];	res[p]=res[lc[p]]+res[rc[p]];
	}
}
void change(int &p,int l,int r,int x){
	if(!p)	p=++cnt;
	if(l==r){mx[p]++;	res[p]=x; return;}
	int mid=l+r>>1;
	if(x<=mid)	change(lc[p],l,mid,x);
	else	change(rc[p],mid+1,r,x);
	push_up(p);
}
int merge(int x,int y,int l,int r){
	if(!x||!y)	return x+y;
	if(l==r){mx[x]+=mx[y]; res[x]=l; return x;}
	int mid=l+r>>1;
	lc[x]=merge(lc[x],lc[y],l,mid);
	rc[x]=merge(rc[x],rc[y],mid+1,r);
	push_up(x);
	return x;
}
void dfs(int x,int fa){
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		dfs(to[i],x); merge(rt[x],rt[to[i]],1,n);
	}
	ans[x]=res[rt[x]];
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	scanf("%lld",&c[i]),change(rt[i],1,n,c[i]);
	for(int i=1,a,b;i<n;i++)	scanf("%lld %lld",&a,&b),add(a,b),add(b,a);
	dfs(1,0);
	for(int i=1;i<=n;i++)	printf("%lld ",ans[i]);puts("");
	return 0;
}