#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;
#pragma GCC optimize(Ofast)
const int N = (int)1e5 + 12, MOD = (int)1e9 + 7;

int B = 19;
int n, c[N], sum = 0, up[N][19];
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 * 8];

void upd(int pos, pair<int, int> val, int v = 1, int tl = 1, int tr = n + 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 + 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;
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> c[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];
        while(v) {
            int col = 1;
            auto r = get1(tin[v], tout[v]);
            for(int i = B - 1; i >= 0; i--) {
                int nv = up[v][i];
                if(nv && get1(tin[nv], tout[nv]) == r) {
                    v = nv;
                    col += (1 << i);
                }
            }
            x.push_back({r.second, col});
            v = up[v][0];
        }
        reverse(x.begin(), x.end());
        ll res = 0;
        int m = (int)x.size();
        for(auto [j, k] : x) {
            res += get(j + 1, n) * 1ll * k;
            cout << j << ' ';
            add(j, k);
        }
        cout << "| ";
        for(auto [j, k] : x) {
            add(j, -k);
        }
        upd(tin[b[i]], {i, c[b[i]]});
        cout << res << '\n';
    }
}

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

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

    while(t--) 
        test();

    return 0;
}