#include <bits/stdc++.h>

#include "joitour.h"

struct ST {
    std::vector<int> data;
    int size;

    ST() = default;
    ST(int n) {
        size = 1 << std::__lg(std::max<int>(1, n - 1)) + 1;
        data.assign(size * 2, 0);
    }

    void add_point(int i, int dlt) {
        for (i += size; i > 0; i >>= 1) {
            data[i] += dlt;
        }
    }

    int get_sum_range(int l, int r) {
        int sum = 0;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                sum += data[l++];
            if (r & 1)
                sum += data[--r];
        }
        return sum;
    }

    int get_sum_point(int i) {
        int sum = 0;
        for (i += size; i > 0; i >>= 1) {
            sum += data[i];
        }
        return sum;
    }

    void add_range(int l, int r, int dlt) {
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                data[l++] += dlt;
            if (r & 1)
                data[--r] += dlt;
        }
    }
};

int n;
std::vector<int> input;
std::vector<std::vector<int>> gr;
std::vector<bool> used;
std::vector<int> sz;
std::vector<int> depth, prv, ctr_deg;
struct Cum {
    int a, c;
    int64_t bc, ba;

    Cum operator-(const Cum& other) const {
        return Cum{a - other.a, c - other.c, bc - other.bc, ba - other.ba};
    }
    Cum operator+(const Cum& other) const {
        return Cum{a + other.a, c + other.c, bc + other.bc, ba + other.ba};
    }
};
std::vector<std::vector<Cum>> count;
struct Fuck {
    int64_t ans_a, ans_b, ans_c;

    Fuck operator-(const Fuck& other) const {
        return Fuck{ans_a - other.ans_a, ans_b - other.ans_b, ans_c - other.ans_c};
    }
    Fuck operator+(const Fuck& other) const {
        return Fuck{ans_a + other.ans_a, ans_b + other.ans_b, ans_c + other.ans_c};
    }

    int64_t get(int i) const {
        return i == 0 ? ans_a : (i == 1 ? ans_b : ans_c);
    }
};
std::vector<Fuck> fuck_ans;
std::vector<std::vector<int>> dist, tin, tout, eul, subtree_num;
std::vector<ST> st_a, st_b, st_c;

Fuck get_ans(Cum val, Cum /* without val */ total) {
    int64_t cum = 0;
    cum += val.a * total.bc;
    cum += val.c * total.ba;
    cum += val.ba * total.c;
    cum += val.bc * total.a;
    Fuck res{cum, cum, cum};
    res.ans_a = val.bc;
    res.ans_b += val.a * int64_t(total.c) + val.c * int64_t(total.a);
    res.ans_c = val.ba;
    return res;
}

int64_t ans;

void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) {
    n = N;
    input = F;
    gr.assign(n, {});
    for (int i = 0; i < n - 1; i++) {
        gr[U[i]].push_back(V[i]);
        gr[V[i]].push_back(U[i]);
    }

    ans = 0;
    sz.assign(n, 0), used.assign(n, false), depth.assign(n, -1), prv.assign(n, -1), ctr_deg.assign(n, -1);
    count.assign(n, {}), fuck_ans.assign(n, Fuck());
    dist.clear(), tin.clear(), tout.clear(), subtree_num.clear(), eul.assign(n, {});
    st_a.assign(n, {}), st_b.assign(n, {}), st_c.assign(n, {});

    auto find = [&](int v) {
        auto dfs = [&](auto dfs, int v, int f) -> void {
            sz[v] = 1;
            for (int t : gr[v]) {
                if (t != f && !used[t]) {
                    dfs(dfs, t, v);
                    sz[v] += sz[t];
                }
            }
        };
        dfs(dfs, v, -1);
        int f = -1;
        int s = sz[v];
        while (true) {
            auto it = std::find_if(gr[v].begin(), gr[v].end(), [&](int t) { return t != f && !used[t] && sz[t] > s / 2; });
            if (it != gr[v].end()) {
                f = v;
                v = *it;
            } else {
                break;
            }
        }
        return v;
    };

    auto build = [&](auto build, int u, int dp, int f) -> void {
        u = find(u);
        used[u] = true;
        depth[u] = dp;
        prv[u] = f;

        if (dist.size() == dp) {
            dist.emplace_back(n, -1);
            tin.emplace_back(n, -1);
            tout.emplace_back(n, -1);
            subtree_num.emplace_back(n, -2);
        }

        auto dfs = [&](auto dfs, int v, int f, int sn) -> int {
            tin[dp][v] = eul[u].size();
            eul[u].push_back(v);
            subtree_num[dp][v] = sn;

            int cnt = 0;
            for (int t : gr[v]) {
                if (t != f && !used[t]) {
                    dfs(dfs, t, v, f == -1 ? cnt : sn);
                    cnt++;
                }
            }
            tout[dp][v] = eul[u].size();
            return cnt;
        };
        int g = ctr_deg[u] = dfs(dfs, u, -1, -1);
        count[u].assign(g + 1, Cum());

        int m = eul[u].size();
        st_a[u] = ST(m), st_b[u] = ST(m), st_c[u] = ST(m);
        for (int i = 1; i < m; i++) {
            int v = eul[u][i];
            int sb = subtree_num[dp][v];

            if (input[v] == 0) {
                count[u][sb].a += 1;
                count[u][sb].ba += st_b[u].get_sum_point(tin[dp][v]);

                st_a[u].add_point(tin[dp][v], +1);
            } else if (input[v] == 2) {
                count[u][sb].c += 1;
                count[u][sb].bc += st_b[u].get_sum_point(tin[dp][v]);

                st_c[u].add_point(tin[dp][v], +1);
            } else {
                count[u][sb].ba += st_a[u].get_sum_range(tin[dp][v], tout[dp][v]);
                count[u][sb].bc += st_c[u].get_sum_range(tin[dp][v], tout[dp][v]);

                st_b[u].add_range(tin[dp][v], tout[dp][v], +1);
            }
        }
        fuck_ans[u] = Fuck();
        for (int i = 0; i < g; i++) {
            fuck_ans[u] = fuck_ans[u] + get_ans(count[u][i], count[u][g]);
            count[u][g] = count[u][g] + count[u][i];
        }
        ans += fuck_ans[u].get(input[u]);

        for (int t : gr[u]) {
            if (!used[t]) {
                build(build, t, dp + 1, u);
            }
        }
    };

    build(build, 0, 0, -1);
}

void change(int v, int y) {
    int y0 = input[v];
    int u = v;
    while (u != -1) {
        int dp = depth[u];
        int sb = subtree_num[dp][v];
        input[v] = y0;

        ans -= fuck_ans[u].get(input[u]);
        if (sb != -1) {
            count[u][ctr_deg[u]] = count[u][ctr_deg[u]] - count[u][sb];
            fuck_ans[u] = fuck_ans[u] - get_ans(count[u][sb], count[u][ctr_deg[u]]);

            if (input[v] == 0) {
                count[u][sb].a -= 1;
                count[u][sb].ba -= st_b[u].get_sum_point(tin[dp][v]);
                st_a[u].add_point(tin[dp][v], -1);
            } else if (input[v] == 2) {
                count[u][sb].c -= 1;
                count[u][sb].bc -= st_b[u].get_sum_point(tin[dp][v]);
                st_c[u].add_point(tin[dp][v], -1);
            } else {
                count[u][sb].ba -= st_a[u].get_sum_range(tin[dp][v], tout[dp][v]);
                count[u][sb].bc -= st_c[u].get_sum_range(tin[dp][v], tout[dp][v]);
                st_b[u].add_range(tin[dp][v], tout[dp][v], -1);
            }
        }

        input[v] = y;

        if (sb != -1) {
            if (input[v] == 0) {
                count[u][sb].a += 1;
                count[u][sb].ba += st_b[u].get_sum_point(tin[dp][v]);
                st_a[u].add_point(tin[dp][v], +1);
            } else if (input[v] == 2) {
                count[u][sb].c += 1;
                count[u][sb].bc += st_b[u].get_sum_point(tin[dp][v]);
                st_c[u].add_point(tin[dp][v], +1);
            } else {
                count[u][sb].ba += st_a[u].get_sum_range(tin[dp][v], tout[dp][v]);
                count[u][sb].bc += st_c[u].get_sum_range(tin[dp][v], tout[dp][v]);
                st_b[u].add_range(tin[dp][v], tout[dp][v], +1);
            }

            fuck_ans[u] = fuck_ans[u] + get_ans(count[u][sb], count[u][ctr_deg[u]]);
            count[u][ctr_deg[u]] = count[u][ctr_deg[u]] + count[u][sb];
        }
        ans += fuck_ans[u].get(input[u]);

        u = prv[u];
    }
}

long long num_tours() {
    // return 0;
    return ans;
}