#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];

    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);
        if (y == -1) val[x] = 0;
        else val[x] = 1;
    }

    void modify1(int x, int y) {
        sum += y * o[1].query(1, dfn[x]);
        o[0].modify(dfn[x], y);
        if (y == -1) val[x] = 0;
        else val[x] = 2;
    }

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

int main() {
  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);
  }
}

/usr/bin/ld: /tmp/ccg6C1Nr.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccruDXCp.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status