#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int N = (int)1e5 + 12, MOD = (int)1e9 + 7;

int B = 18, p[N];
int n, c[N], sum = 0, up[N][18];
void make() {
    vector<int> cl;
    for(int i = 1; i <= n; i++) {
        cl.push_back(c[i]);
    }
    sort(cl.begin(), cl.end());
    cl.resize(unique(cl.begin(), cl.end()) - cl.begin());
    for(int i = 1; i <= n; i++) {
        c[i] = lower_bound(cl.begin(), cl.end(), c[i]) - cl.begin() + 1;
    }
}
int t[N], a[N], b[N], tin[N], tout[N];
vector<int> g[N];
pair<int, int> s[N * 4];
void upd(int pos, pair<int, int> val, int v = 1, int tl = 1, int tr = n) {
    if(tl == tr) {
        s[v] = val; 
    } else {
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos, val, v + v, tl, tm);
        else upd(pos, val, v + v + 1, tm + 1, tr);
        s[v] = max(s[v + v], s[v + v + 1]);
    }
}
pair<int, int> get1(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if(l > r || tl > r || l > tr) return {0, 0};
    if(tl >= l && tr <= r) return s[v];
    int tm = (tl + tr) >> 1;
    return max(get1(l, r, v + v, tl, tm), get1(l, r, v + v + 1, tm + 1, tr));
}
void add(int pos, int val) {
    while(pos <= n) {
        t[pos] += val;
        pos += pos & -pos;
    }
}
int get(int i) {
    int ret = 0;
    while(i) {
        ret += t[i];
        i -= i & -i;
    }
    return ret;
}
int get(int l, int r) {
    return get(r) - get(l - 1);
}
void edge(int u, int v) {
    up[v][0] = u;
    g[u].push_back(v);
    for(int i = 1; i < B; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
}   
int timer = 0;

void dfs(int v) {
    tin[v] = ++timer;
    for(int to : g[v]) {
        dfs(to);
    }
    tout[v] =timer;
}
bool is(int v, int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int f(int v, int vv) {
    if(p[v] == v || !is(vv, p[v])) return v;
    return p[v] = f(p[v], vv);
}
bool vis[N];
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
        p[i] = i;
    }
    make();

    for(int i = 1; i <= n - 1; i++) {
        cin >> a[i] >> b[i];
        edge(a[i], b[i]);
    }
    dfs(1);
    upd(tin[1],{0, c[1]});
    for(int i = 1; i <= n - 1; i++) {
        vector<pair<int, int>> x;
        int v = a[i];
        vis[b[i]] = 1;
        vector<pair<int, int>> e;
        e.emplace_back(a[i], b[i]);
        while(v) {
            int col = 1;
            int val = f(v, v);
            for(int i = B - 1; i >= 0; i--) {
                int nv = up[v][i];
                if(nv && f(nv, nv) == val) {
                    v = nv;
                    col += (1 << i);
                }
            }
            // cout << v << ' ' << f(v) << '\n';
            if(up[v][0]) e.emplace_back(up[v][0], v);
            x.push_back({c[val], col});
            v = up[v][0];
        }
        for(auto [j, t]: e) {
            p[f(j, j)] = t;
        }
        // cout << f(2) << "x\n";
        reverse(x.begin(), x.end());
        sum += (int)x.size();assert(sum <= 20 * n);
        ll res = 0;
        int m = (int)x.size();
        for(auto [j, k] : x) {
            res += get(j + 1, n) * 1ll * k;
            add(j, k);
        }
        for(auto [j, k] : x) {
            add(j, -k);
        }
        cout << res << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) 
        test();

    return 0;
}