CF600E

// Problem: E. Lomsat gelral
// Contest: Codeforces - Educational Codeforces Round 2
// URL: https://codeforces.com/problemset/problem/600/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;
using a2l = array<ll, 2>;

#if 0
// 启发式合并
int main(int argc, char **argv)
{
    int n, x, y;
    cin >> n;
    vi vc(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> vc[i];
    vector<vi> g(n + 1);
    for (int i = 1; i < n; ++i)
        cin >> x >> y, g[x].push_back(y), g[y].push_back(x);
    vl ans(n + 1);
    vi dl(n + 1), dr(n + 1), dv(n + 1);
    vi dson(n + 1), dsize(n + 1);
    int cur_cnt = 0;
    function<int(int, int)> dfs_cnt = [&](int u, int fa) {
        int ret = 1, son_id = 0, son_cnt = 0;
        dl[u] = cur_cnt++;
        dv[dl[u]] = u;
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            int sub_cnt = dfs_cnt(v, u);
            if (sub_cnt > son_cnt)
                son_cnt = sub_cnt, son_id = v;
            ret += sub_cnt;
        }
        dr[u] = cur_cnt;
        dson[u] = son_id;
        return dsize[u] = ret;
    };
    dfs_cnt(1, -1);

    vi ccnt(n + 1);
    ll accumulated_color_score = 0;
    int max_appearance = -1;
    auto inc_color_cnt = [&](int u) -> ll {
        auto &c = ccnt[vc[u]];
        c++;
        if (c > max_appearance) {
            max_appearance = c;
            accumulated_color_score = vc[u];
        } else if (c == max_appearance) {
            accumulated_color_score += vc[u];
        }
        return accumulated_color_score;
    };
    auto clear_color_cnt = [&]() {
        accumulated_color_score = 0;
        max_appearance = -1;
    };
    function<void(int, int, int)> dfs = [&](int u, int pa, int persist) {
        for (auto v : g[u]) {
            if (v == pa || v == dson[u])
                continue;
            dfs(v, u, 0);
        }
        if (dson[u])
            dfs(dson[u], u, 1);

        for (auto v : g[u]) {
            if (v == pa || v == dson[u])
                continue;
            for (int k = dl[v]; k < dr[v]; ++k)
                inc_color_cnt(dv[k]);
        }
        ans[u] = inc_color_cnt(u);

        if (persist == 0) {
            for (int k = dl[u]; k < dr[u]; ++k)
                ccnt[vc[dv[k]]]--;
            clear_color_cnt();
        }
    };
    dfs(1, -1, 1);
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
    return 0;
};
#else
// 线段树
struct SegTree {
    struct NodeInfo {
        ll acc, max_freq;
        NodeInfo operator+(const NodeInfo &n) const
        {
            NodeInfo ret{0ll, 0ll};
            if (max_freq < n.max_freq)
                ret = n;
            else if (max_freq == n.max_freq)
                ret = NodeInfo{acc + n.acc, max_freq};
            else
                ret = *this;
            return ret;
        };
    };
    int ncnt;
    vi root, ls, rs;
    vector<NodeInfo> tr;
    SegTree(int n) : ncnt(1)
    {
        root = vi(n);
        ls = rs = vi(n << 5);
        tr = vector<NodeInfo>(n << 5, NodeInfo{0ll, 0ll});
    }
    void popup(int rt) { tr[rt] = tr[ls[rt]] + tr[rs[rt]]; }
    void update(int &rt, int pos, int l, int r)
    {
        if (rt == 0)
            rt = ncnt++;
        if (l == r) {
            tr[rt].acc = pos;
            tr[rt].max_freq++;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid)
            update(ls[rt], pos, l, mid);
        else
            update(rs[rt], pos, mid + 1, r);
        popup(rt);
    }
    int merge(int rt1, int rt2, int l, int r) // merge rt2 into rt1
    {
        if (rt1 == 0 || rt2 == 0)
            return rt1 + rt2;
        if (l == r) {
            tr[rt1].max_freq += tr[rt2].max_freq;
            return rt1;
        }
        int mid = l + r >> 1;
        ls[rt1] = merge(ls[rt1], ls[rt2], l, mid);
        rs[rt1] = merge(rs[rt1], rs[rt2], mid + 1, r);
        popup(rt1);
        return rt1;
    }
    void out(int rt1, int l, int r, int lvl)
    {
        for (int i = 0; i < lvl; ++i)
            cerr << ' ';
        fprintf(stderr, "%d:%d~%d:%lld,%lld\n", rt1, l, r, tr[rt1].acc, tr[rt1].max_freq);
        int mid = l + r >> 1;
        if (l != r) {
            out(ls[rt1], l, mid, lvl + 1);
            out(rs[rt1], mid + 1, r, lvl + 1);
        }
    }
};
int main(int argc, char **argv)
{
    int n, x, y;
    cin >> n;
    vi vc(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> vc[i];
    vector<vi> g(n + 1);
    for (int i = 1; i < n; ++i)
        cin >> x >> y, g[x].push_back(y), g[y].push_back(x);
    vl ans(n + 1);
    SegTree seg(n + 1);
    function<void(int, int)> dfs = [&](int u, int fa) {
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            dfs(v, u);
            seg.root[u] = seg.merge(seg.root[u], seg.root[v], 1, n);
        }
        seg.update(seg.root[u], vc[u], 1, n);
        // dbg("insert ", u, vc[u]);
        ans[u] = seg.tr[seg.root[u]].acc;
        // seg.out(seg.root[u], 1, n, 0);
        // cerr << endl;
    };
    dfs(1, -1);
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
};
#endif