#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define INF 1000000001LL
#define POT (1LL<<23)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define FCTCST 7
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U,typename Z>
pair<T, U> operator*(const pair<T, U>& a, const Z& b) {
return {a.first*b, a.second*b};
}
template<typename T, typename U,typename Z>
pair<T, U> operator/(const pair<T, U>& a, const Z& b) {
return {a.first/b, a.second/b};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
os<<"{"<<p.ff<<", "<<p.ss<<"}";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
for (size_t i = 0; i < v.size(); ++i) {
if (i) os << ", ";
os << v[i];
}
os << "}";
return os;
}
template<ll MOD=998244353>
struct mint_t{
ll x;
mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;}
mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;}
mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;}
mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;}
mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;}
mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;}
mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;}
mint_t fp(ll y)const{
mint_t a=1,b=x;
while(y){
if(y&1)a*=b;
b*=b;
y/=2;
}
return a;
}
mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;}
mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;}
};
#define mint mint_t<>
template<long long MOD>
istream& operator>>(istream& in, mint_t<MOD>& a){
ll x;
in>>x;
a=mint_t<MOD>(x);
return in;
}
template<long long MOD>
istream& operator<<(istream& out, mint_t<MOD>& a){
out<<a.x;
return out;
}
mint fct[FCTCST];
mint bnm(ll a,ll b){
if(b>a || a<0)return 0;
return fct[a]/fct[b]/fct[a-b];
}
ll kol[200007];
struct st{
ll x1,x2,x3,x4,x5,x6,x7,x8,x9;
};
st get(ll v){
return {0,(kol[v]==0),(kol[v]==2),0,0,(kol[v]==1),0,0,0};
}
st lift(st x){
x.x6=x.x7=x.x8=0;return x;
}
st add(st x,ll v){
if(kol[v]==1){x.x1+=x.x9;
x.x4+=x.x2;
x.x5+=x.x3;
x.x6++;
}
else if(kol[v]==0) {x.x1+=x.x5;
x.x2++;
}
else{x.x1+=x.x4;
x.x3++;
}
x.x7=x.x5;
x.x8=x.x4;
x.x9=0;
return x;
}
st on1(st x,st y){//point
x.x9+=y.x9+x.x2*y.x3+x.x3*y.x2;
x.x1+=y.x1+x.x2*y.x5+x.x5*y.x2+x.x3*y.x4+x.x4*y.x3;
x.x2+=y.x2;
x.x3+=y.x3;
x.x4+=y.x4;
x.x5+=y.x5;
return x;
}
st on2(st x,st y){//path
x.x1+=y.x1+x.x4*y.x3+x.x5*y.x2+x.x2*y.x7+x.x3*y.x8;
x.x7+=y.x7+y.x3*x.x6;
x.x8+=y.x8+y.x2*x.x6;
x.x4+=y.x4+x.x2*y.x6;
x.x5+=y.x5+x.x3*y.x6;
x.x2+=y.x2;
x.x3+=y.x3;
x.x6+=y.x6;
return x;
}
ll n,q;
vi g[200008],d[200008],mj[200007];
ll sz[200007],par[200007];
void dfs(ll v,ll p){
par[v]=p;
sz[v]=1;
ll mx=0;
for(ll i:g[v])if(i^p){dfs(i,v);sz[v]+=sz[i];mx=max(mx,sz[i]);}
for(ll i=0;i<g[v].size();i++){
if(g[v][i]==p)continue;
if(mx==sz[g[v][i]])d[v].insert(d[v].begin(),g[v][i]),mx=0;
else d[v].pb(g[v][i]);
}
}
void wyp(st x){
cout<<" {"<<x.x1<<", "<<x.x2<<", "<<x.x3<<", "<<x.x4<<", "<<x.x5<<", "<<x.x6<<", "<<x.x7<<", "<<x.x8<<", "<<x.x9<<"} ";
}
void df2(ll v,ll x){
mj[x].pb(v);
if(d[v].size())df2(d[v][0],x);
for(ll i=1;i<d[v].size();i++)df2(d[v][i],d[v][i]);
}
void init(int N,vector<int>kl,vector<int>u,vector<int>v,int Q){
n=N;
q=Q;
for(ll i=0;i<n;i++){
kol[i]=kl[i];
}
for(ll i=0;i<n-1;i++){
g[u[i]].pb(v[i]);g[v[i]].pb(u[i]);
}
dfs(0,0);
df2(0,0);
// for(ll i=0;i<n;i++){
// cout<<mj[i]<<" "<<d[i]<<"\n";
// }
}
st pol(ll v,ll l,ll r,bool tp){//if(rand()%100==0)exit(0);
if(l==r){
if(tp==0){
st pm=lift(pol(d[v][l],0,mj[d[v][l]].size()-1,1));
// cout<<v<<" "<<l<<" "<<r<<" "<<tp<<" ";wyp(pm);cout<<endl;
return pm;
}
else{
if(d[mj[v][l]].size()<2)return get(mj[v][l]);
st pm=add(pol(mj[v][l],1,d[mj[v][l]].size()-1,0),mj[v][l]);
// cout<<v<<" "<<l<<" "<<r<<" "<<tp<<" ";wyp(pm);cout<<endl;
return pm;
}
}
else{
if(tp==0){
ll rs=0;
for(ll i=l;i<=r;i++)rs+=sz[d[v][i]];
ll r2=sz[d[v][l]];
ll md;
for(ll i=l+1;i<=r;i++){
r2+=sz[d[v][i]];
if(r2*2>rs){md=i-1;break;}
}
st pm=on1(pol(v,l,md,0),pol(v,md+1,r,0));
// cout<<v<<" "<<l<<" "<<r<<" "<<tp<<" ";wyp(pm);cout<<endl;
return pm;
}
else{
ll rs=0;
ll r2;
for(ll i=l;i<=r;i++){
ll x=sz[mj[v][i]];
if(i+1<mj[v].size())x-=sz[mj[v][i+1]];
rs+=x;
if(i==l)r2=x;
}
ll md;
for(ll i=l+1;i<=r;i++){
ll x=sz[mj[v][i]];
if(i+1<mj[v].size())x-=sz[mj[v][i+1]];
r2+=x;
if(r2*2>rs){md=i-1;break;}
}
//cout<<md<<" "<<l<<" m ";
st pm=on2(pol(v,md+1,r,1),pol(v,l,md,1));
// cout<<v<<" "<<l<<" "<<r<<" "<<tp<<" ";wyp(pm);cout<<endl;
return pm;
}
}
}
ll num_tours(){
return pol(0,0,mj[0].size()-1,1).x1;
}
void change(int v,int x){
kol[v]=x;
}
#include <cassert>
#include <cstdio>
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);
}
}
