#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, L = 1e6;

struct op {
    int l, r, c;
    long long sB, sW;
} p[N << 5];

int a[N], rt[N << 1], tot;

int newNode(int l, int r) {
    ++tot, p[tot].l = p[tot].r = p[tot].c = 0;
    p[tot].sB = 0, p[tot].sW = 1ll * r * r - 1ll * (l - 1) * (l - 1);
    return tot;
}

void up(int k, int l, int r) {
    int mid = (l + r) >> 1;
    if (!p[k].l) p[k].l = newNode(l, mid);
    if (!p[k].r) p[k].r = newNode(mid + 1, r);
    p[k].c = p[p[k].l].c ^ p[p[k].r].c;
    p[k].sB = p[p[k].r].sB + (p[p[k].r].c ? p[p[k].l].sW : p[p[k].l].sB);
    p[k].sW = p[p[k].r].sW + (p[p[k].r].c ? p[p[k].l].sW : p[p[k].l].sB);
}

void modify(int &k, int l, int r, int x) {
    if (!k) k = newNode(l, r);
    if (l == r) {
        p[k].sB = l + l - 1, p[k].sW = 0, p[k].c = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) modify(p[k].l, l, mid, x);
    else modify(p[k].r, mid + 1, r, x);
    up(k, l, r);
}

long long res;

int merge(int x, int y, int l, int r, int c1, int c2) {
    if (!x && !y) {
        if (c1 && c2) res += 1ll * r * r - 1ll * (l - 1) * (l - 1);
        return 0;
    }
    if (!x) {
        if (c1) res += !c2 ? p[y].sB : p[y].sW;
        return y;
    }
    if (!y) {
        if (c2) res += !c1 ? p[x].sB : p[x].sW;
        return x;
    }
    if (l == r) {
        if ((p[x].c ^ c1) && (p[y].c ^ c2)) res += l + l - 1;
        p[x].c ^= p[y].c;
        if (p[y].c) swap(p[x].sB, p[x].sW);
        return x;
    }
    int mid = (l + r) >> 1;
    p[x].r = merge(p[x].r, p[y].r, mid + 1, r, c1, c2);
    p[x].l = merge(p[x].l, p[y].l, l, mid, c1 ^ p[p[x].r].c ^ p[p[y].r].c, c2 ^ p[p[y].r].c);
    up(x, l, r);
    return x;
}

signed main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] >>= 1;
    for (int i = 1; i <= n; ++i) modify(rt[i], 1, L, a[i]);
    for (int i = 1, x, y; i < n; ++i) {
        scanf("%d%d", &x, &y);
        res = 0;
        rt[n + i] = merge(rt[x], rt[y], 1, L, 0, 0);
        printf("%lld\n", res << 2);
    }
    return 0;
}