#include <bits/stdc++.h>
#include "joitour.h"

using namespace std;

const int N = 2e5 + 5;

int n, a[N];
vector<int> G[N];
long long S;
int dep[N], fa[N], siz[N], son[N], top[N], dfn[N];

void dfs1(int x) {
    siz[x] = 1;
    for (auto v : G[x]) {
        if (v == fa[x]) continue;
        fa[v] = x, dep[v] = dep[x] + 1;
        dfs1(v);
        siz[x] += siz[v];
        if (siz[v] > siz[son[x]]) son[x] = v;
    }
}

void dfs2(int x) {
    dfn[x] = ++dfn[0];
    if (!son[x]) return;
    int v = son[x];
    top[v] = top[x];
    dfs2(v);
    for (auto w : G[x]) {
        if (w == fa[x] || w == son[x]) continue;
        dfs2(top[w] = w);
    }
}

struct TreeArray {
    int s[N];

    void modify(int x, int y) {
        for (; x <= n; x += x & -x) s[x] += y;
    }

    int query(int x) {
        int res = 0;
        for (; x; x -= x & -x) res += s[x];
        return res;
    }

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

struct DS1 {
    TreeArray o[2];
    long long sum;
    int val[N];

    struct core {
        int cnt[1 << 19], val[1 << 19], lz[1 << 19];
        long long sum[1 << 19];

        void pushdown(int k) {
            if (lz[k]) {
                lz[k << 1] += lz[k], sum[k << 1] += 1ll * cnt[k << 1] * lz[k];
                lz[k << 1 | 1] += lz[k], sum[k << 1 | 1] += 1ll * cnt[k << 1 | 1] * lz[k];
                val[k << 1] += lz[k], val[k << 1 | 1] += lz[k];
                lz[k] = 0;
            }
        }

        void modify1(int k, int l, int r, int x, int y) {
            cnt[k] += y;
            if (l == r) {
                sum[k] = cnt[k] * val[k];
                return;
            }
            pushdown(k);
            int mid = (l + r) >> 1;
            if (x <= mid) modify1(k << 1, l, mid, x, y);
            else modify1(k << 1 | 1, mid + 1, r, x, y);
            sum[k] = sum[k << 1] + sum[k << 1 | 1];
        }

        void modify2(int k, int l, int r, int x, int y, int v) {
            if (l > y || r < x) return;
            if (l >= x && r <= y) {
                lz[k] += v, sum[k] += cnt[k] * v, val[k] += v;
                return;
            }
            pushdown(k);
            int mid = (l + r) >> 1;
            modify2(k << 1, l, mid, x, y, v);
            modify2(k << 1 | 1, mid + 1, r, x, y, v);
            sum[k] = sum[k << 1] + sum[k << 1 | 1];
        }

        long long query(int k, int l, int r, int x, int y) {
            if (l > y || r < x) return 0;
            if (l >= x && r <= y) return sum[k];
            pushdown(k);
            int mid = (l + r) >> 1;
            return query(k << 1, l, mid, x, y) + query(k << 1 | 1, mid + 1, r, x, y);
        }
    } dta;

    void modify0(int x, int y) {
        sum += y * o[0].query(dfn[x], dfn[x] + siz[x] - 1);
        o[1].modify(dfn[x], y);
        o[1].modify(dfn[x] + siz[x], -y);
        val[x] += y;
        dta.modify1(1, 1, n, dfn[x], y);
    }

    void modify1(int x, int y) {
        sum += y * o[1].query(1, dfn[x]);
        o[0].modify(dfn[x], y);
        while (x) {
            dta.modify2(1, 1, n, dfn[top[x]], dfn[x], y);
            if (x != 1) {
                dta.modify2(1, 1, n, max(dfn[top[x]] - 1, 1), dfn[x] - 1, y);
            }
            x = fa[top[x]];
        }
    }

    long long query(int x) {
        long long ans = sum;
        ans += 1ll * o[0].query(1, n) * o[1].query(1, dfn[x]);
        while (x) {
            if (x != top[x]) ans -= dta.query(1, 1, n, dfn[top[x]], dfn[x] - 1);
            if (val[fa[top[x]]]) {
                ans -= o[0].query(dfn[top[x]], dfn[top[x]] + siz[top[x]] - 1);
                ans -= o[0].query(dfn[fa[top[x]]], dfn[fa[top[x]]] + siz[fa[top[x]]] - 1);
            }
            x = fa[top[x]];
        }
        return ans;
    }
} d0, d2;

struct DS2 {
    TreeArray o[2];

    struct Core {
        long long res[N];
        int cnt[2][N];

        void modify(int ty, int x, int y) {
            while (x) {
                res[fa[top[x]]] -= 1ll * cnt[0][top[x]] * cnt[1][top[x]];
                cnt[ty][top[x]] += y;
                res[fa[top[x]]] += 1ll * cnt[0][top[x]] * cnt[1][top[x]];
                x = fa[top[x]];
            }
        }

        long long query(int x) {
            return res[x];
        }
    } dta;

    pair<int, int> get(int x) {
        return {o[0].query(dfn[x], dfn[x] + siz[x] - 1),
                o[1].query(dfn[x], dfn[x] + siz[x] - 1)};
    }

    void modify(int ty, int x, int y) {
        o[ty].modify(dfn[x], y);
        dta.modify(ty, x, y);
    }

    long long query(int x) {
        int tot0, tot1, inner0, inner1;
        tie(tot0, tot1) = get(1);
        tie(inner0, inner1) = get(x);
        long long res = 1ll * tot0 * tot1 - 1ll * (tot0 - inner0) * (tot1 - inner1);
        if (!son[x]) return res;
        int tct0, tct1;
        tie(tct0, tct1) = get(son[x]);
        res -= tct0 * tct1;
        res -= dta.query(x);
        return res;
    }
} d1;

void modify(int x, int y, int z) {
    if (y == 0) {
        S += z * d0.query(x);
        d1.modify(0, x, z);
        d2.modify1(x, z);
    } else if (y == 1) {
        S += z * d1.query(x);
        d0.modify0(x, z);
        d2.modify0(x, z);
    } else if (y == 2) {
        S += z * d2.query(x);
        d0.modify1(x, z);
        d1.modify(1, x, z);
    }
}

void init(int tn, vector<int> ta, vector<int> ox, vector<int> oy, int) {
    n = tn;
    for (int i = 1; i <= n; ++i) a[i] = ta[i - 1];
    for (int i = 1, x, y; i < n; ++i) {
        x = ox[i - 1] + 1, y = oy[i - 1] + 1;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs1(dep[1] = 1), dfs2(top[1] = 1);
    for (int i = 1; i <= n; ++i) {
        modify(i, a[i], 1);
    }
}

void change(int x, int y) {
    ++x;
    if (y == a[x]) return;
    modify(x, a[x], -1);
    a[x] = y;
    modify(x, a[x], 1);
}

long long num_tours() {
    return S;
}