条了数小时了 /kel

#include <bits/stdc++.h>
// #define int long long
// #define double long double
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define endl '\n' 
using namespace std;
typedef long long ll;
const int N = 1e5+5;

struct node{
	int l,r;
	ll sum,ans;
}t[N<<2];

int n,m,c[N],r[N];
vector<int> v[N];

inline void push_up(int k){
	if(t[t[k].l].sum > t[t[k].r].sum){
		t[k].sum = t[t[k].l].sum;
		t[k].ans = t[t[k].l].ans;
	}else if(t[t[k].l].sum < t[t[k].r].sum){
		t[k].sum = t[t[k].r].sum;
		t[k].ans = t[t[k].r].ans;
	}else{
		t[k].sum = t[t[k].l].sum;
		t[k].ans = t[t[k].l].ans+t[t[k].r].ans;
	}
}

inline void update(int &k,int l,int r,int pos,int val){
	if(!k) k = ++m;
	if(l == r){
		t[k].sum += val;
		t[k].ans = l;
		return ;
	}
	
	int mid = l + r >> 1;
	if(pos <= mid) update(t[k].l,l,mid,pos,val);
	else update(t[k].r,mid+1,r,pos,val);
	push_up(k);
}

inline int merge(int k,int c,int l,int r){
	if(!k || !c) return max(k,c);
	if(l == r){
		t[k].sum += t[c].sum;
		t[k].ans = l;
		return k;
	}
	
	int mid = l + r >> 1;
	t[k].l = merge(t[k].l,t[c].l,l,mid);
	t[k].r = merge(t[k].r,t[c].r,mid+1,r);
	push_up(k);
	return k;
}

inline int dfs(int k,int f){ 
	int size = v[k].size();
	for(int i = 0; i < size; i++){
		if(v[k][i] = f) continue;
		dfs(v[k][i],k);
		merge(r[k],r[v[k][i]],1,1e5);
	}
	update(r[k],1,1e5,c[k],1);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> c[i];
		r[i] = i;
	}
	
	m = n;
	
	int x,y;
	for(int i = 1; i < n; i++){
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	
	dfs(1,0);
	
	for(int i = 1; i <= n; i++)
		cout << t[i].ans << " ";
	cout << endl;
	return 0; 
}