#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define pb push_back
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){
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){
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 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]);
}
st mp[1000007];
void init(int N,vector<int>kl,vector<int>u,vector<int>v,int Q){
for(ll i=0;i<1000007;i++)mp[i].x1=-1;
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);
}
map<pair<pair<ll,ll>,pair<ll,bool>>,ll>mp2,mp3;
ll ak=1;
ll pp[1000007],mjj[200007];
ll moj[1000007][4];
st pol(ll v,ll l,ll r,bool tp,ll pop){
ll ja;
if(mp2[{{v,l},{r,tp}}]==0){
ja=ak++;mp2[{{v,l},{r,tp}}]=ja;}
else ja=mp2[{{v,l},{r,tp}}];
if(mp[ja].x1!=-1)return mp[ja];
pp[ja]=pop;
moj[ja][0]=v;moj[ja][1]=l;moj[ja][2]=r;moj[ja][3]=tp;
if(l==r){
if(tp==0){
st pm=lift(pol(d[v][l],0,mj[d[v][l]].size()-1,1,ja));
mp[ja]=pm;
return pm;
}
else{
mjj[mj[v][l]]=ja;
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,ja),mj[v][l]);
mp[ja]=pm;
return pm;
}
}
else{
if(tp==0){
ll md;
if(mp3[{{v,l},{r,tp}}])md=mp3[{{v,l},{r,tp}}]-1;
else{
ll rs=0;
for(ll i=l;i<=r;i++)rs+=sz[d[v][i]];
ll r2=sz[d[v][l]];
for(ll i=l+1;i<=r;i++){
r2+=sz[d[v][i]];
if(r2*2>rs){md=i-1;break;}
}
mp3[{{v,l},{r,tp}}]=md+1;}
st pm=on1(pol(v,l,md,0,ja),pol(v,md+1,r,0,ja));
mp[ja]=pm;
return pm;
}
else{
ll md;
if(mp3[{{v,l},{r,tp}}])md=mp3[{{v,l},{r,tp}}]-1;
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;
}
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;}
}
mp3[{{v,l},{r,tp}}]=md+1;
}
st pm=on2(pol(v,md+1,r,1,ja),pol(v,l,md,1,ja));
mp[ja]=pm;
return pm;
}
}
}
ll num_tours(){
return pol(0,0,mj[0].size()-1,1,-1).x1;
}
void change(int v,int x){
kol[v]=x;
ll y=mjj[v];
while(y!=-1){
mp[y].x1=-1;
y=pp[y];
}
}
