#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[3];
    long long sum;
    int val[N], s[N];

    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);
        o[2].modify(dfn[x], y);
        o[2].modify(dfn[x] + siz[x], -y);
        val[x] += y;
    }

    void modify1(int x, int y) {
        sum += y * o[1].query(1, dfn[x]);
        o[0].modify(dfn[x], y);
        for (int i = x; i; i = fa[i]) {
            s[i] += y;
        }
    }

    long long query(int x) {
        long long ans = sum;
        ans += 1ll * o[0].query(1, n) * o[2].query(1, dfn[x]);
        for (int i = x; i; i = fa[i]) {
            ans -= (s[i] + s[fa[i]]) * val[fa[i]];
        }
        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 -= 1ll * 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;
}