#include "joitour.h"
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native,sse,sse2,sse3")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=31,Mxn=6e6,base=131;
//#undef int
int n,k,m,q,L,T;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int F[mxn+10];
vector<int>adj[mxn+10];
enum Type{Vertex,Compress,Rake,AddEdge,AddVertex};
struct sttree{
int root,stroot;
vector<int>P,L,R;
vector<Type>T;
int ct;
void init(int x){
root=x;
build();
}
private:
int gethvy(int cur,int p){
int best=0,sz=1;
for(auto &i:adj[cur])if(i!=p){
int x=gethvy(i,cur);
sz+=x;
if(x>best)best=x,swap(adj[cur][0],i);
}
//if(adj[cur].size())cout<<cur<<" "<<adj[cur][0]<<"?\n";
return sz;
}
int add(int k,int l,int r,Type t){
if(k==-1)k=++ct;
L[k]=l,R[k]=r,T[k]=t;
if(l!=-1)P[l]=k;
if(r!=-1)P[r]=k;
return k;
}
pii merge(vector<pii>have,Type t){
if(have.size()==1)return have[0];
int cs=0;
for(auto i:have)cs+=i.s;
vector<pii>a,b;
for(auto i:have){
if(i.s<cs)a.pb(i);
else b.pb(i);
cs-=2*i.s;
}
pii x=merge(a,t),y=merge(b,t);
return {add(-1,x.f,y.f,t),x.s+y.s};
}
pii compress(int cur){
vector<pii>have={addvertex(cur)};
while(adj[cur].size())cur=adj[cur][0],have.pb(addvertex(cur));
return merge(have,Type::Compress);
}
pii rake(int cur){
vector<pii>have;
for(int i=1;i<adj[cur].size();i++)have.pb(addedge(adj[cur][i]));
return have.empty()? (pii){-1,0} : merge(have,Type::Rake);
}
pii addedge(int cur){
pii x=compress(cur);
return {add(-1,x.f,-1,Type::AddEdge),x.s};
}
pii addvertex(int cur){
pii x=rake(cur);
return {add(cur,x.f,-1,(x.f==-1)?Type::Vertex : Type::AddVertex),x.s+1};
}
void build(){
P.resize(4*n+1,-1),L.resize(4*n+1,-1),R.resize(4*n+1,-1);
T.resize(4*n+1);
ct=n;
gethvy(root,-1);
stroot=compress(root).f;
}
};
struct path{
int dp[3][3],ca=0;
int c12=0,c10=0;
path(){
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)dp[i][j]=0;
}
}
};
struct point{
int dp[3][3],ca=0,ca2=0;
point(){for(int i=0;i<3;i++)for(int j=0;j<3;j++)dp[i][j]=0;}
};
path vertex(int i){
path x;
x.dp[F[i]][F[i]]++;
return x;
}
path compress(path a,path b){
path x;
x.ca+=a.ca+b.ca;
x.dp[0][1]=a.dp[0][0]*b.dp[1][1];
x.dp[0][2]=(a.dp[0][0]*b.dp[1][2])+(a.dp[0][1]*b.dp[2][2]);
x.dp[1][0]=(a.dp[1][1]*b.dp[0][0]);
x.dp[1][2]=(a.dp[1][1]*b.dp[2][2]);
x.dp[2][1]=a.dp[2][2]*b.dp[1][1];
x.dp[2][0]=(a.dp[2][2]*b.dp[1][0])+(a.dp[2][1]*b.dp[0][0]);
x.ca+=a.c10*b.dp[2][2];
x.ca+=b.c10*a.dp[2][2];
x.ca+=a.c12*b.dp[0][0];
x.ca+=b.c12*a.dp[0][0];
//cout<<a.c12<<" "<<b.dp[0][0]<<'\n';
x.c10=a.c10+b.c10;
x.c12=a.c12+b.c12;
for(int i=0;i<3;i++)for(int j=0;j<3;j++)x.dp[i][j]+=a.dp[i][j]+b.dp[i][j];
//cout<<a.dp[0][0]<<"UM\n";
return x;
}
point rake(point a,point b){
point x;
x.ca+=(a.dp[0][0]*b.dp[1][2])+(a.dp[1][0]*b.dp[2][2])+(a.dp[2][2]*b.dp[1][0])+(a.dp[1][2]*b.dp[0][0]);
x.ca+=a.ca+b.ca;
x.ca2=a.ca2+b.ca2+(a.dp[0][0]*b.dp[2][2])+(a.dp[2][2]*b.dp[0][0]);
for(int i=0;i<3;i++)for(int j=0;j<3;j++)x.dp[i][j]=a.dp[i][j]+b.dp[i][j];
return x;
}
path addvertex(point a,int i){
path x;
x.c10=a.dp[1][0];
x.c12=a.dp[1][2];
x.ca=a.ca;
x.dp[0][0]=a.dp[0][0];
x.dp[2][2]=a.dp[2][2];
x.dp[F[i]][F[i]]++;
if(F[i]==0){
x.ca+=a.dp[1][2];
}
else if(F[i]==2){
x.ca+=a.dp[1][0];
}
else{
x.ca+=a.ca2;
x.c10+=a.dp[0][0];
x.c12+=a.dp[2][2];
}
return x;
}
point addedge(path a){
point x;
x.ca=a.ca+a.dp[2][0]+a.dp[0][2];
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)if(i==j||i==1){
x.dp[i][j]=a.dp[i][j];
if(i!=j)x.dp[j][i]+=a.dp[i][j];
}
}
x.dp[1][0]+=a.c10;
x.dp[1][2]+=a.c12;
//cout<<x.dp[0][0]<<"KKK\n";
return x;
}
vector<path>Path;
vector<point>Point;
sttree stt;
void update(int cur){
if(stt.T[cur]==Type::Vertex){
Path[cur]=vertex(cur);
}
if(stt.T[cur]==Type::Compress){
Path[cur]=compress(Path[stt.L[cur]],Path[stt.R[cur]]);
}
if(stt.T[cur]==Type::Rake){
Point[cur]=rake(Point[stt.L[cur]],Point[stt.R[cur]]);
}
if(stt.T[cur]==Type::AddEdge){
Point[cur]=addedge(Path[stt.L[cur]]);
}
if(stt.T[cur]==Type::AddVertex){
Path[cur]=addvertex(Point[stt.L[cur]],cur);
}
}
void dfs(int cur){
if(cur==-1)return;
dfs(stt.L[cur]);
dfs(stt.R[cur]);
//cout<<cur<<" "<<stt.L[cur]<<" "<<stt.R[cur]<<'\n';
update(cur);
}
vector<int>adj2[mxn+10];
void getadj(int cur,int p){
for(auto i:adj2[cur])if(i!=p){
adj[cur].pb(i);
getadj(i,cur);
}
}
void init(int32_t N, std::vector<int32_t> FF, std::vector<int32_t> U, std::vector<int32_t> V,int32_t Q) {
n=N;
for(int i=0;i<n-1;i++)adj2[U[i]].pb(V[i]),adj2[V[i]].pb(U[i]);
getadj(0,-1);
for(int i=0;i<n;i++)F[i]=FF[i];
Path.resize(4*n+1);
Point.resize(4*n+1);
stt.init(0);
dfs(stt.stroot);
}
void change(int32_t x, int32_t y){
F[x]=y;
while(x!=-1){
update(x);
x=stt.P[x];
}
}
long long num_tours(){
return Path[stt.stroot].ca+Path[stt.stroot].dp[2][0]+Path[stt.stroot].dp[0][2];
}
/*
*/
