#pragma GCC optimize("O3") 
#pragma GCC target("avx2") 
#pragma GCC optimize("unroll-loops") 
  
#pragma GCC optimize("Ofast,unroll-loops") 
#pragma GCC target("avx,avx2,fma,sse4") 

#include "joitour.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>

using namespace std;

struct Fenwick {
    int n;
    vector<int> tree;

    Fenwick() {}

    void build(int x) {
        n = x;
        tree.resize(n + 1);
    }

    int get_sum(int ind){
        int ans = 0;
        for (int i = ind; i >= 0; i = (i & (i + 1)) - 1){
            ans += tree[i];
        }
        return ans;
    }

    void upd(int ind, int x){
        for (int i = ind; i < n; i = (i | (i + 1))){
            tree[i] += x;
        }
    }

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

struct Fenwick2 {
    int n;
    vector<int> tree;

    Fenwick2() {}

    void build(int x) {
        n = x;
        tree.resize(n + 3);
    }

    int get(int ind) {
        int ans = 0;
        for (int i = ind; i >= 0; i = (i & (i + 1)) - 1){
            ans += tree[i];
        }
        return ans;
    }

    void upd(int ind, int x) {
        for (int i = ind; i < n; i = (i | (i + 1))){
            tree[i] += x;
        }
    }

    void upd(int l, int r, int x) {
        upd(l, x);
        upd(r + 1, -x);
    }
};
vector<vector<int>> g;
vector<vector<int>> gr;
vector<int> col;

long long anss = 0;

struct HLD {
    map<int, int> gt;
    vector<int> ord, backord, uppest, c, sz;
    vector<long long> ct01, ct21, ct0, ct2;
    vector<Fenwick> lol;
    Fenwick2 lol1;
    int timer = 1;
    long long ans = 0, tans = 0;

    void dfssz(int v, int p) {
        if (p != -1) {
            for (int i = 0; i < (int)gr[v].size() - 1; ++i) {
                if (gr[v][i] == p) {
                    swap(gr[v][i], gr[v][i + 1]);
                }
            }
            if (gr[v].size()) gr[v].pop_back();
        }
        if (p == -1) {
            for (auto e : gr[v]) {
                uppest[e] = e;
            }
        } else {
            for (auto e : gr[v]) {
                uppest[e] = uppest[v];
            }
        }
        sz[v] = 1;
        for (auto e : gr[v]) {
            dfssz(e, v);
            ct0[v] += ct0[e];
            ct2[v] += ct2[e];
            ct01[v] += ct01[e];
            ct21[v] += ct21[e];
            sz[v] += sz[e];
        }
        if (c[v] == 0) {
            ct0[v]++;
        }
        if (c[v] == 2) {
            ct2[v]++;
        }
        if (c[v] == 1) {
            ct01[v] += ct0[v];
            ct21[v] += ct2[v];
        }
    }

    void dfs(int v) {
        backord[v] = ord.size();
        ord.push_back(v);
        if (gr[v].size() == 0) return;
        for (auto &e : gr[v]) {
            if (sz[e] > sz[gr[v][0]]) {
                swap(e, gr[v][0]);
            }
        }
        for (auto e : gr[v]) {
            dfs(e);
        }
    }

    HLD(){}

    void upd(int v, int x) {
        lol1.upd(backord[v], backord[v] + sz[v] - 1, x);
    }

    int get1s(int v) {
        return lol1.get(backord[v]);
    }

    int get0s(int v) {
        return lol[0].su(backord[v], backord[v] + sz[v] - 1);
    }

    int get2s(int v) {
        return lol[2].su(backord[v], backord[v] + sz[v] - 1);
    }

    void build(vector<int> kek) {
        gr.clear();
        int n = (int)kek.size();
        gr.resize(n);
        for (int i = 0; i < n; ++i) gt[kek[i]] = i;
        c.resize(n);
        for (int i = 0; i < n; ++i) {
            c[i] = col[kek[i]];
            for (auto e : g[kek[i]]) {
                if (gt.find(e) != gt.end()) {
                    gr[i].push_back(gt[e]);
                }
            }
        }
        uppest.resize(n);
        backord.resize(n);
        sz.resize(n);
        ct0.resize(n);
        ct2.resize(n);
        ct01.resize(n);
        ct21.resize(n);
        dfssz(0, -1);
        dfs(0);
        lol.resize(3);
        lol1.build(n);
        for (int i = 0; i < 3; ++i) {
            if (i == 1) continue;
            lol[i].build(n);
        }
        for (int i = 0; i < n; ++i) {
            if (c[ord[i]] == 1) continue;
            lol[c[ord[i]]].upd(i, 1);
        }
        for (int i = 0; i < n; ++i) {
            if (c[ord[i]] == 1) {
                upd(ord[i], 1);
            }
        }
        for (auto e : gr[0]) {
            ans += ct01[e] * (ct2[0] - ct2[e]);
            ans += ct21[e] * (ct0[0] - ct0[e]);
            int T = ct2[0] - ct2[e];
            if (c[0] == 2) T--;
            tans += ct0[e] * T;
        }
    }

    long long get01(int v) {
        if (c[0] == 1) return ct01[0] - ct01[v] - ct0[0];
        return ct01[0] - ct01[v];
    }

    long long get21(int v) {
        if (c[0] == 1) return ct21[0] - ct21[v] - ct2[0];
        return ct21[0] - ct21[v];
    }

    void kek1(int v, int col) {
        v = gt[v];
        if (v == 0) {
            if (c[v] == 2) {
                ans -= ct01[0];
                ct2[v]--;
                lol[2].upd(backord[v], -1);
            }
            if (c[v] == 0) {
                ans -= ct21[0];
                ct0[v]--;
                lol[0].upd(backord[v], -1);
            }
            if (c[v] == 1) {
                ct01[v] -= ct0[v];
                ct21[v] -= ct2[v];
                upd(0, -1);
            }
            c[v] = col;
            if (c[v] == 2) {
                ans += ct01[0];
                ct2[v]++;
                lol[2].upd(backord[v], 1);
            }
            if (c[v] == 0) {
                ans += ct21[0];
                ct0[v]++;
                lol[0].upd(backord[v], 1);
            }
            if (c[v] == 1) {
                ct01[v] += ct0[v];
                ct21[v] += ct2[v];
                upd(0, 1);
            }
            return;
        }
        int t = uppest[v];
        int e = t;
        if (c[v] == 0) {
            int TT = get1s(v);
            if (c[0] == 1) TT--;
            ans -= TT * (ct2[0] - ct2[t]);
            ans -= get21(t);
            ct0[t]--;
            ct01[t] -= get1s(v);
            if (c[0] == 1) ct01[t]++;
            ct0[0]--;
            ct01[0] -= get1s(v);
            lol[0].upd(backord[v], -1);
            int T = ct2[0] - ct2[t];
            if (c[0] == 2) T--;
            tans -= T;
        }
        if (c[v] == 1) {
            ans -= get0s(v) * (ct2[0] - ct2[t]);
            ans -= get2s(v) * (ct0[0] - ct0[t]);
            ct01[0] -= get0s(v);
            ct21[0] -= get2s(v);
            ct01[t] -= get0s(v);
            ct21[t] -= get2s(v);
            upd(v, -1);
        }
        if (c[v] == 2) {
            int TT = get1s(v);
            if (c[0] == 1) TT--;
            ans -= TT * (ct0[0] - ct0[t]);
            ans -= get01(t);
            // cout << c[0] << ' ';
            // cout << get01(t) << ' ' << get1s(v) * (ct0[0] - ct0[t]) << ' ' << ans << ' ';
            ct2[t]--;
            ct21[t] -= get1s(v);
            if (c[0] == 1) ct21[t]++;
            ct2[0]--;
            ct21[0] -= get1s(v);
            lol[2].upd(backord[v], -1);
            int T = ct0[0] - ct0[t];
            if (c[0] == 0) T--;
            tans -= T;
        }
        c[v] = col;
        if (c[v] == 0) {
            int TT = get1s(v);
            if (c[0] == 1) TT--;
            ans += TT * (ct2[0] - ct2[t]);
            ans += get21(t);
            ct0[t]++;
            ct01[t] += get1s(v);
            if (c[0] == 1) ct01[t]--;
            ct0[0]++;
            ct01[0] += get1s(v);
            lol[0].upd(backord[v], 1);
            int T = ct2[0] - ct2[t];
            if (c[0] == 2) T--;
            tans += T;
        }
        if (c[v] == 1) {
            ans += get0s(v) * (ct2[0] - ct2[t]);
            ans += get2s(v) * (ct0[0] - ct0[t]);
            ct01[0] += get0s(v);
            ct21[0] += get2s(v);
            ct01[t] += get0s(v);
            ct21[t] += get2s(v);
            upd(v, 1);
        }
        if (c[v] == 2) {
            int TT = get1s(v);
            if (c[0] == 1) TT--;
            ans += TT * (ct0[0] - ct0[t]);
            ans += get01(t);
            ct2[t]++;
            ct21[t] += get1s(v);
            if (c[0] == 1) ct21[t]--;
            ct2[0]++;
            ct21[0] += get1s(v);
            lol[2].upd(backord[v], 1);
            int T = ct0[0] - ct0[t];
            if (c[0] == 0) T--;
            tans += T;
        }
        e = t;
    }

    long long getans() {
        if (c[0] == 1) return ans + tans;
        return ans;
    }
};

vector<HLD> lol;
vector<int> sz, cc, ord;
vector<vector<int>> p;

void dfssz(int v, int pr) {
    sz[v] = 1;
    for (auto e : g[v]) {
        if (e == pr) continue;
        if (cc[e] != -1) continue;
        dfssz(e, v);
        sz[v] += sz[e];
    }
    ord.push_back(v);
}

void find_centroid(int v, int d) {
    ord.clear();
    dfssz(v, -1);
    int N = sz[v];
    int cntr = -1;
    for (auto &e : ord) {
        if (sz[e] > N / 2) {
            cntr = e;
            swap(e, ord[0]);
            break;
        }
    }
    lol[cntr].build(ord);
    cc[cntr] = d;
    for (auto e : ord) {
        p[d][e] = cntr;
    }
    for (auto e : g[cntr]) {
        if (cc[e] == -1) {
            find_centroid(e, d + 1);
        }
    }
}

void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) {
    g.resize(N);
    sz.resize(N);
    p.resize(20, vector<int>(N));
    cc.resize(N, -1);
    col = F;
    for (int i = 0; i < N - 1; ++i) {
        g[U[i]].push_back(V[i]);
        g[V[i]].push_back(U[i]);
    }
    lol.resize(N);
    find_centroid(0, 0);
    for (auto e : lol) anss += e.getans();
}

void change(int X, int Y) {
    for (int i = 0; i <= cc[X]; ++i) {
        anss -= lol[p[i][X]].getans();
        lol[p[i][X]].kek1(X, Y);
        anss += lol[p[i][X]].getans();
    }
}

long long num_tours() {
    return anss;
}

#ifdef LOCAL 

int main() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  int N;
  assert(scanf("%d", &N) == 1);

  std::vector<int> F(N);
  for (int i = 0; i < N; i++) {
    assert(scanf("%d", &F[i]) == 1);
  }

  std::vector<int> U(N - 1), V(N - 1);
  for (int j = 0; j < N - 1; j++) {
    assert(scanf("%d %d", &U[j], &V[j]) == 2);
  }

  int Q;
  assert(scanf("%d", &Q) == 1);

  init(N, F, U, V, Q);
  printf("%lld\n", num_tours());
  fflush(stdout);

  for (int k = 0; k < Q; k++) {
    int X, Y;
    assert(scanf("%d %d", &X, &Y) == 2);

    change(X, Y);
    printf("%lld\n", num_tours());
    fflush(stdout);
  }
}


#endif

In file included from /usr/include/c++/13/vector:63,
                 from joitour.h:1,
                 from answer.code:8:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~