#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN =  1e5 + 500;
const int OFF = (1 << 18);

int n;
int niz[MAXN], sazet[MAXN];
vector<int> v, bizut;
set<int> vek[2 * MAXN];
int roots[2 * MAXN],l[2 * OFF], r[2 * OFF], lazy[2 * OFF], vel[2 * MAXN];
ll val[2 * OFF];
int cnt;

void novi () {
    l[cnt] = -1;
    r[cnt] = -1;
    cnt++;
}

void prop (int x, ll lo, ll hi) {
    if (lazy[x] == 0) return;
    ll uk = 4 * hi * hi;
    if (lo > 0) uk -= 4 * lo * lo;
//    cout << "BLOOOOOOOOOOOOOOOOOOB " << x << ' ' << uk << ' ' << val[x] << "\n";
    val[x] = uk - val[x];
    if (hi - lo > 1) {
        if (l[x] == -1) {
            l[x] = cnt;
            novi ();
        }
        if (r[x] == -1) {
            r[x] = cnt;
            novi ();
        }
//        cout << "BIIIIIIIIIIIIRB " << l[x] << ' ' << r[x] << "\n";
        lazy[l[x]] = (lazy[l[x]] ^ 1);
        lazy[r[x]] = (lazy[r[x]] ^ 1);
    }
    lazy[x] = 0;
}

void update (int a, int b, int x, int lo = 0, int hi = OFF) {
    prop (x, lo, hi);
    if (hi <= a || lo >= b) return;

    if (lo >= a && hi <= b) {
//        cout << a << ' ' << b << ' ' << x << ' ' << lo << ' ' << hi << "\n";
        lazy[x] = 1;
        prop (x, lo, hi);
        return;
    }

    int mid = (lo + hi) / 2;

    if (l[x] == -1) {
        l[x] = cnt;
        novi ();
    }
    if (r[x] == -1) {
        r[x] = cnt;
        novi ();
    }
    update (a, b, l[x], lo, mid);
    update (a, b, r[x], mid, hi);
    val[x] = val[l[x]] + val[r[x]];
}

ll query (int a, int b, int x, int lo = 0, int hi = OFF) {
//    cout << a << ' ' << b << ' ' << x << ' ' << lo << ' ' << hi << "    "  << val[x] << "\n";
    if (hi <= a || lo >= b) return 0;
    prop (x, lo, hi);

    if (lo >= a && hi <= b) {
//        cout << "AAAAAAA " << val[x] << "\n";
        return val[x];
    }

    int mid = (lo + hi) / 2;
    if (l[x] == -1) {
        l[x] = cnt;
        novi ();
    }
    if (r[x] == -1) {
        r[x] = cnt;
        novi ();
    }
    return query (a, b, l[x], lo, mid) + query (a, b, r[x], mid, hi);
}

ll spoji (int x, int y) {
    ll cijena = 0;
    bizut.clear ();
    for (auto it: vek[y]) bizut.push_back(it);
    for (int i = (int) bizut.size () - 1; i >= 0; i-=2) {
        int iduc = 0;
        if (i > 0) iduc = bizut[i - 1];

        cijena += query (iduc, bizut[i], roots[x]);
        update (iduc, bizut[i], roots[x]);
    }
    for (auto it: vek[y]) vek[x].insert (it);
    vek[y].clear ();

    return cijena;
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> niz[i];
        niz[i] /= 2;
    }
    for (int i = 0; i < n; i++) v.push_back (niz[i]);

    sort (v.begin (), v.end ());
    v.resize (unique (v.begin (), v.end ()) - v.begin ());

    for (int i = 0; i < n; i++) {
        sazet[i] = lower_bound (v.begin (), v.end (), niz[i]) - v.begin ();
        roots[i] = cnt;
        vel[i] = 1;
        novi ();
        update (0, niz[i], roots[i]);
        vek[i].insert (niz[i]);
    }

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--;b--;

        if (vel[b] > vel[a]) swap (a, b);
        cout << spoji (a, b) << "\n";

        roots[n + i] = roots[a];
        swap (vek[n + i], vek[a]);
        vel[n + i] = vel[a] + vel[b];
    }

    return 0;
}