#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 1e5 + 7;

ll pref[N];

struct Info {
    ll ans[2];
    int tag = 0, lx = 0, rx = 0, L = 0, R = 0;

    void rev() {
        tag ^= 1;
        swap(ans[0], ans[1]);
    }

    Info() = default;
    Info(int l, int r) : lx(l), rx(r), tag(0), L(0), R(0) {
        ans[0] = 0, ans[1] = pref[r] - pref[l];
    }
};

Info t[N * 50];
int top = 1;

int create(int l, int r) {
    t[top++] = Info(l, r);
    return top - 1;
}

void push(int x) {
    if (!t[x].L) {
        t[x].L = create(t[x].lx, t[x].lx + t[x].rx >> 1);
    }
    if (!t[x].R) {
        t[x].R = create(t[x].lx + t[x].rx >> 1, t[x].rx);
    }
}

void pull(int x) {
    int lx = t[x].lx, rx = t[x].rx, mid = lx + rx >> 1;
    t[x].ans[0] = t[x].ans[1] = 0;
    if (!t[x].L) {
        t[x].ans[1] = pref[mid] - pref[lx];
    } else {
        t[x].ans[1] = t[t[x].L].ans[1];
        t[x].ans[0] = t[t[x].L].ans[0];
    }
    if (!t[x].R) {
        t[x].ans[1] += pref[rx] - pref[mid];
    } else {
        t[x].ans[1] += t[t[x].R].ans[1];
        t[x].ans[0] += t[t[x].R].ans[0];
    }
    if (t[x].tag) {
        swap(t[x].ans[0], t[x].ans[1]);
    }
}

void rangeApply(int x, int l, int r) {
    if (t[x].lx >= r || l >= t[x].rx) {
        return;
    }
    if (l <= t[x].lx && t[x].rx <= r) {
        return t[x].rev();
    }
    push(x);
    rangeApply(t[x].L, l, r);
    rangeApply(t[x].R, l, r);
    pull(x);
}

int query(int x, int i) {
    if (x == 0) {
        return 0;
    } else if (t[x].lx + 1 == t[x].rx) {
        return t[x].tag;
    } else {
        return t[x].tag ^ query(i < (t[x].lx + t[x].rx >> 1) ? t[x].L : t[x].R, i);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] /= 2;
    }

    vector<int> yy = a;
    sort(yy.begin(), yy.end());
    yy.resize(unique(yy.begin(), yy.end()) - yy.begin());
    const int m = size(yy);

    auto func = [&](int l, int r)-> ll {
        l -= 1, r -= 1;
        return (r - l + 1) + 1LL * r * (r + 1) - 1LL * l * (l - 1);
    };

    for (int i = 1; i <= m; ++i) {
        pref[i] = pref[i - 1] + func(i == 1 ? 1 : yy[i - 2] + 1, yy[i - 1]);
    }

    vector<int> roots(2 * n);
    vector<set<int>> st(2 * n);

    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(yy.begin(), yy.end(), a[i]) - yy.begin();
        roots[i] = create(0, m);
        a[i] += 1;
        rangeApply(roots[i], 0, a[i]);
        st[i] = {a[i]};
    }

    cout << endl;

    for (int i = 0; i + 1 < n; ++i) {
        int x, y;
        cin >> x >> y;
        x -= 1, y -= 1;
        ll init = (t[roots[x]].ans[0] + t[roots[y]].ans[0]);
        if (st[x].size() > st[y].size()) {
            swap(x, y);
        }
        int last = 0;
        for (int c : st[x]) {
            st[y].insert(c);
            if (query(roots[x], c - 1)) {
                rangeApply(roots[y], last, c);
            }
            last = c;
        }
        cout << 2 * (init - t[roots[y]].ans[0]) << '\n';
        st[x].clear();
        roots[n + i] = roots[y];
        swap(st[n + i], st[y]);
    }

    return 0;
}