问题求答

#include<bits/stdc++.h>
#define int long long
#define lson tr[rt].l
#define rson tr[rt].r
using namespace std;
int n;
const int N = 100007;
int color[N],mn=INT_MAX,mx=INT_MIN;
int e[N*2],h[N*2],hd[N*2],cnt,ans[N],tot;


//--------------------------------------
struct ZJQ{
	int l,r,ans,cnt;
}tr[4000005];//为什么这里开的是4000005
//难道不应该开N*4*N吗
//N个结点*N棵线段树(解释)
//--------------------------------------


void add(int a,int b){
	++cnt;
	e[cnt]=b;
	hd[cnt]=h[a];
	h[a]=cnt;
}
void push_up(int rt){
	if(tr[lson].cnt>tr[rson].cnt){
		tr[rt].cnt=tr[lson].cnt;
		tr[rt].ans=tr[lson].ans;
	}
	if(tr[lson].cnt<tr[rson].cnt){
		tr[rt].cnt=tr[rson].cnt;
		tr[rt].ans=tr[rson].ans;
	}
	if(tr[lson].cnt==tr[rson].cnt){
		tr[rt].cnt=tr[lson].cnt;
		tr[rt].ans=tr[lson].ans+tr[rson].ans;
	}
}
void merge(int &rt1,int rt2,int l,int r){
	if(!rt1 or !rt2){rt1+=rt2;return ;}
	if(l==r){
		tr[rt1].cnt+=tr[rt2].cnt;
		return ;
	}
	int mid=(r+l)/2;
	merge(tr[rt1].l,tr[rt2].l,l,mid);
	merge(tr[rt1].r,tr[rt2].r,mid+1,r);
	push_up(rt1);
}
void modify(int &rt,int l,int r,int x,int v){
	if(!rt) rt=++tot;
	if(l==r){tr[rt].ans=x,tr[rt].cnt+=v;return ;}
	int mid=(l+r)/2;
	if(x<=mid) modify(lson,l,mid,x,v);
	else modify(rson,mid+1,r,x,v);
	push_up(rt);
}
void dfs(int rt,int fa){
	for(int i=h[rt];i;i=hd[i]){
		if(e[i]==fa) continue ;
		dfs(e[i],rt);
		merge(rt,e[i],mn,mx);
	}
	modify(rt,mn,mx,color[rt],1);
	ans[rt]=tr[rt].ans;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>color[i];++tot;
		mn=min(mn,color[i]);
		mx=max(mx,color[i]);
	}
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}