#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int mxn=2e5+5;
vi f,g[mxn];int n;ll ans=0;
int tin[mxn][18],tout[mxn][18],cnt[18]{0},ids[mxn][18]{0};
int lv[mxn]{0},pr[mxn]{0};
struct lazy{
int t[4*mxn]{0},lz[4*mxn]{0};
void push(int i,int l,int r){
t[i]+=lz[i];
if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
lz[i]=0;
}
void update(int i,int l,int r,int tl,int tr,int a){
push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lz[i]+=a;push(i,l,r);return;
}int m=(l+r)>>1;update(2*i,l,m,tl,tr,a);update(2*i+1,m+1,r,tl,tr,a);
}
int qr(int i,int l,int r,int idx){
push(i,l,r);
if(r<idx||l>idx)return 0;
if(l==r)return t[i];
int m=(l+r)>>1;
return max(qr(2*i,l,m,idx),qr(2*i+1,m+1,r,idx));
}
}t1[3][18];
struct seg{
int t[4*mxn]{0};
void update(int i,int l,int r,int idx,int v){
if(r<idx||l>idx)return;
if(l==r)return void(t[i]+=v);
int m=(l+r)>>1;update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
t[i]=t[2*i]+t[2*i+1];
}
int qr(int i,int l,int r,int tl,int tr){
if(r<tl||l>tr)return 0;
if(r<=tr&&l>=tl)return t[i];
int m=(l+r)>>1;
return qr(2*i,l,m,tl,tr)+qr(2*i+1,m+1,r,tl,tr);
}
}t2[3][18];
int sz[mxn];
bool vis[mxn]{0};
int getsz(int u,int p){
sz[u]=1;
for(auto v:g[u]){
if(v==p||vis[v])continue;
sz[u]+=getsz(v,u);
}return sz[u];
}
int getct(int u,int p,int rs){
for(auto v:g[u]){
if(v==p||vis[v])continue;
if(sz[v]*2>rs)return getct(v,u,rs);
}return u;
}
vl dp[7][mxn];
ll tdp[7][mxn]{0};
// dp[0]->0,dp[1]->1,dp[2]->2,dp[3]->0,1,dp[4]->1,2,dp[5]->2,1,dp[6]->1,0
void get01234(int u,int p,int x,int id){
dp[f[u]][x][id]++;ids[u][lv[x]]=id;
if(f[u]==1)dp[3][x][id]+=dp[0][x][id];
if(f[u]==2)dp[4][x][id]+=dp[1][x][id];
tin[u][lv[x]]=++cnt[lv[x]];
for(int i=0;i<3;i++)t1[i][lv[x]].update(1,1,n,tin[u][lv[x]],tin[u][lv[x]],dp[i][x][id]);
for(auto v:g[u]){
if(vis[v]||v==p)continue;
get01234(v,u,x,id);
}tout[u][lv[x]]=cnt[lv[x]];
}
void get56(int u,int p,int x,int id){
for(auto v:g[u]){
if(vis[v]||v==p)continue;
get56(v,u,x,id);
}t2[f[u]][lv[x]].update(1,1,n,tin[u][lv[x]],1);
if(f[u]==2)dp[5][x][id]+=t2[1][lv[x]].qr(1,1,n,tin[u][lv[x]],tout[u][lv[x]]);
if(f[u]==1)dp[6][x][id]+=t2[0][lv[x]].qr(1,1,n,tin[u][lv[x]],tout[u][lv[x]]);
}
void play(int u,int p,int l){
int x=getct(u,u,getsz(u,u));vis[x]=1;int id=0;
lv[x]=l;pr[u]=p;tin[x][lv[x]]=++cnt[lv[x]];
for(auto v:g[x]){
if(vis[v])continue;
for(int i=0;i<7;i++)dp[i][x].pb(0);
get01234(v,u,x,id);get56(v,u,x,id);
for(int i=0;i<7;i++)tdp[i][x]+=dp[i][x][id];id++;
}tout[x][lv[x]]=cnt[lv[x]];
for(auto v:g[x]){
if(vis[v])continue;
ans+=dp[0][x][ids[v][lv[x]]]*(tdp[4][x]-dp[4][x][ids[v][lv[x]]]);
ans+=dp[6][x][ids[v][lv[x]]]*(tdp[2][x]-dp[2][x][ids[v][lv[x]]]);
if(f[x]==1){
ans+=dp[0][x][ids[v][lv[x]]]*(tdp[2][x]-dp[2][x][ids[v][lv[x]]]);
}
}
if(f[x]==2)ans+=tdp[6][x];
if(f[x]==0)ans+=tdp[4][x];
for(auto v:g[x]){
if(vis[v])continue;
play(v,x,l+1);
}
}
void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V,int Q){
f=F,n=N;for(int i=0;i<N-1;i++)g[U[i]].pb(V[i]),g[V[i]].pb(U[i]);
play(0,-1,0);
}
void change(int X, int Y){
}
long long num_tours() {
return ans;
}
