600e.cpp

#include "bits/stdc++.h"
#define all(v) begin(v), end(v)
using namespace std;
using ll = int64_t;

const int N = 1e5 + 7;

int n;
int c[N];
vector<int> G[N];

int leaf[N];
struct tree_t { 
    int *lo, *hi;
    int * begin(){ return lo; }
    int * end(){ return hi; }
    size_t size(){ return hi - lo; }
} T[N];
int _E[N], *et = _E;
size_t pre(int i){
    *(T[i].lo = et++) = leaf[i] = i;
    auto s = 0;
    for(auto j : G[i])
        if(!T[j].size() && s < pre(j))
            s = T[j].size(), leaf[i] = leaf[j];
    T[i].hi = et;
    return T[i].size();
}

ll A[N], sum[N];
map<int, int> freq[N];
int bst[N];

void add(int l, int i){
    freq[l][c[i]]++;
    if(bst[l] < freq[l][c[i]])
        bst[l] = freq[l][c[i]], sum[l] = c[i];
    else if(bst[l] == freq[l][c[i]])
        sum[l] += c[i];
}

int main(){
    scanf(" %d", &n);
    for(int i = 0; i < n; i++)
        scanf(" %d", c + i);
    for(int k = 0; k < n - 1; k++){
        int i, j;
        scanf(" %d%d", &i, &j); --i; --j;
        G[i].push_back(j);
        G[j].push_back(i);
    }
    pre(0);
    for(int *it = T[0].end(); it != T[0].begin(); it--){
        int i = *(it - 1);
        add(leaf[i], i);
        for(auto j : G[i])
            if(T[j].size() < T[i].size() && leaf[i] != leaf[j])
                for(auto u : T[j])
                    add(leaf[i], u);
        A[i] = sum[leaf[i]];
    }

    for(int i = 0; i < n; i++)
        printf("%lld%c", A[i], " \n"[i + 1 == n]);
}