#include "joitour.h"
#include <bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define int ll
#define mod 998244353
#define sz(x) (int)((x).size())
using namespace std;
const int N=200005;
namespace
{
	struct node
	{
		int s0,s1,s2,s01,s10,s12,s21,s012,s210,coef;
		node()
		{
			s0=s1=s2=s01=s10=s12=s21=s012=s210=coef=0;
		}
	};
	int dfn[N],idfn[N],DFN;
	int sfn[N],isfn[N],SFN;
	int lfn[N],rfn[N];
	int Tp[N],db[N];
	int siz[N],son[N];
	poly G[N];
	int col[N];
	int ffa[N];
	int rtc[N],rt[N];
	int n;
}
node fh(node x,node y)
{
	node res=x;

	res.s0+=y.s0;
	res.s1+=y.s1;
	res.s2+=y.s2;
	res.s01+=y.s01;
	res.s10+=y.s10;
	res.s12+=y.s12;
	res.s21+=y.s21;
	res.s012+=y.s012;
	res.s210+=y.s210;

	res.s012+=x.s0*y.s12;
	res.s012+=x.s10*y.s2;
	res.s210+=x.s2*y.s10;
	res.s210+=x.s12*y.s0;
	res.coef+=y.coef;
	return res;
}
node merge(node x,node y)
{
	node res;
	res.s0=x.s0+y.s0;
	res.s1=x.s1+y.s1;
	res.s2=x.s2+y.s2;
	res.s012=x.s012+y.s012+x.s0*y.s12+x.s01*y.s2;
	res.s210=x.s210+y.s210+x.s2*y.s10+x.s21*y.s0;
	res.s01=(x.s01+y.s01+x.s0*y.s1);
	res.s10=(x.s10+y.s10+x.s1*y.s0);
	res.s12=(x.s12+y.s12+x.s1*y.s2);
	res.s21=(x.s21+y.s21+x.s2*y.s1);
	return res;
}
node Qry(int k);
namespace sg
{
    node tr[N<<1];
    int ls[N<<1],rs[N<<1],md[N<<1];
    int cnt;
    inline void build(int &k,int l,int r)
    {
        if (l>r) return;
        k=++cnt;
        if (l==r) return;
        int mid=l+(r-l)/2;
        mid=max(mid,l);
        mid=min(mid,r-1);
        md[k]=mid;
        build(ls[k],l,mid);
        build(rs[k],mid+1,r);
    }
    void upd(int k,int l,int r,int L)
    {
        if (l>r) return;
        if (l==r)
        {
            int u=isfn[l];
            tr[k]=node();
			tr[k]=Qry(u);
			tr[k].coef=tr[k].s0*tr[k].s2;
			// cout<<k<<"..."<<l<<" "<<r<<" "<<tr[k].s0<<" "<<tr[k].s1<<" "<<tr[k].s2<<endl;
            return;
        }
        int mid=md[k];
        if (L<=mid)
            upd(ls[k],l,mid,L);
        else
            upd(rs[k],mid+1,r,L);
        tr[k]=fh(tr[ls[k]],tr[rs[k]]);
			// cout<<k<<"..."<<l<<" "<<r<<" "<<tr[k].s0<<" "<<tr[k].s1<<" "<<tr[k].s2<<endl;
    }
    node query(int k,int l,int r,int L,int R)
    {
        if (L==0||L>R) return node();
        if (L<=l&&r<=R) return tr[k];
        int mid=md[k];
        if (R<=mid) return query(ls[k],l,mid,L,R);
        if (L>mid) return query(rs[k],mid+1,r,L,R);
        return fh(query(ls[k],l,mid,L,R),query(rs[k],mid+1,r,L,R));
    }
}
//seg_for_chain
namespace CL
{
    int cnt;
    node tr[N<<1];
    int ls[N<<1],rs[N<<1],md[N<<1];
    inline void build(int &k,int l,int r)
    {
        if (l>r) return;
        k=++cnt;
        if (l==r) return;
        int mid=l+(r-l)/2;
        md[k]=mid;
        build(ls[k],l,mid);
        build(rs[k],mid+1,r);
    }
	void pushup(int k)
    {
		tr[k]=merge(tr[ls[k]],tr[rs[k]]);
    }
    void upd(int k,int l,int r,int L)
    {
        if (l==r)
        {
            int u=idfn[l];
			tr[k]=node();
            if (rt[u]) tr[k]=sg::tr[rt[u]];
			if (col[u]==0)
			{
				tr[k].s012+=tr[k].s12;
				tr[k].s01+=tr[k].s1;
				tr[k].s0++;
			} else
			if (col[u]==1)
			{
				// cout<<"?????"<<u<<" "<<tr[k].s0<<" "<<tr[k].s2<<" "<<tr[k].coef<<endl;
				tr[k].s012+=tr[k].s0*tr[k].s2-tr[k].coef;
				tr[k].s12+=tr[k].s2;
				tr[k].s10+=tr[k].s0;
				tr[k].s1++;
			} else
			if (col[u]==2)
			{
				tr[k].s210+=tr[k].s10;
				tr[k].s21+=tr[k].s1;
				tr[k].s2++;
			}
			tr[k].s21=0;
			tr[k].s01=0;
			tr[k].s21=tr[k].s12;
			tr[k].s01=tr[k].s10;
			tr[k].s1=(col[u]==1);
			// cout<<"ppp "<<k<<": "<<u<<" "<<l<<" "<<r<<" "<<tr[k].s0<<" "<<tr[k].s1<<" "<<tr[k].s2<<endl;
			// cout<<tr[k].s01<<" "<<tr[k].s12<<" "<<endl;
			// cout<<tr[k].s21<<" "<<tr[k].s10<<" "<<endl;
			// cout<<tr[k].s012+tr[k].s210<<endl;
            return;
        }
        int mid=md[k];
        if (L<=mid) upd(ls[k],l,mid,L);
        else upd(rs[k],mid+1,r,L);
        pushup(k);
		// cout<<"ppp "<<k<<" "<<l<<" "<<r<<" "<<tr[k].s0<<" "<<tr[k].s1<<" "<<tr[k].s2<<endl;
		// 	cout<<tr[k].s01<<" "<<tr[k].s12<<" "<<endl;
		// 	cout<<tr[k].s21<<" "<<tr[k].s10<<" "<<endl;
		// 	cout<<tr[k].s012+tr[k].s210<<endl;
    }
    node query(int k,int l,int r,int L,int R)
    {
        if (L>R) return node();
        if (L<=l&&r<=R) return tr[k];
        int mid=md[k];
        if (R<=mid) return query(ls[k],l,mid,L,R);
        if (L>mid) return query(rs[k],mid+1,r,L,R);
        return merge(query(ls[k],l,mid,L,R),query(rs[k],mid+1,r,L,R));
    }
}
void dfs(int k,int fa)
{
    siz[k]=1;son[k]=0;
	ffa[k]=fa;
	for (int i=0;i<sz(G[k]);i++)
	{
		int u=G[k][i];
		if (u==fa) continue;
		dfs(u,k);
        siz[k]+=siz[u];
        if (siz[u]>siz[son[k]]) son[k]=u;
	}
}
void dfs1(int k,int tp)
{
    Tp[k]=tp;
    dfn[k]=++DFN;
    idfn[DFN]=k;
    db[k]=k;
    if (son[k]) dfs1(son[k],tp),db[k]=db[son[k]];
	for (int i=0;i<sz(G[k]);i++)
	{
		int u=G[k][i];
        if (u==son[k]||u==ffa[k]) continue;
		dfs1(u,u);
	}
	for (int i=0;i<sz(G[k]);i++)
	{
		int u=G[k][i];
		if (u==son[k]||u==ffa[k]) continue;
        sfn[u]=++SFN;
        isfn[SFN]=u;
    }
}
void dfs2(int k,int fa)
{
	for (auto u:G[k])
	{
		if (u==fa) continue;
		dfs2(u,k);
	}
	CL::upd(rtc[Tp[k]],dfn[Tp[k]],dfn[db[k]],dfn[k]);
	if (sfn[k]) 
	{
		// cout<<"upd "<<ffa[k]<<" "<<k<<" "<<sfn[k]<<" "<<col[k]<<endl;
		sg::upd(rt[ffa[k]],lfn[ffa[k]],rfn[ffa[k]],sfn[k]);
	}
}
node Qry(int k)
{
	// cout<<"Qry "<<k<<" "<<CL::tr[rtc[k]].s0<<" "<<CL::tr[rtc[k]].s1<<" "<<CL::tr[rtc[k]].s2<<endl;
	return CL::tr[rtc[k]];
}
void init(signed nn, std::vector<signed> F, std::vector<signed> U, std::vector<signed> V,
          signed Q)
{
	n=nn;
	for (int i=0;i<n;i++) col[i+1]=F[i];
	// cout<<"?"<<n<<endl;
	for (int i=0;i<sz(U);i++)
	{
		G[U[i]+1].push_back(V[i]+1);
		G[V[i]+1].push_back(U[i]+1);
	}
	dfs(1,0);
	dfs1(1,1);
    for (int i=1;i<=n;i++)
        if (Tp[i]==i)
        {
            CL::build(rtc[i],dfn[Tp[i]],dfn[db[i]]);
        }
    for (int i=1;i<=n;i++)
        if (G[i].size())
        {
			int l=0,r=0;
			for (auto u:G[i])
				if (!(u==ffa[i]||u==son[i]))
				{
					if (!l) l=sfn[u];
					r=sfn[u];
				}
			if (!l) continue;
			lfn[i]=l,rfn[i]=r;
			sg::build(rt[i],l,r);
        }
	dfs2(1,0);
	node now=CL::tr[rtc[1]];
}
void change(signed x, signed y) 
{
	x++;
	col[x]=y;
	while (x)
	{
		CL::upd(rtc[Tp[x]],dfn[Tp[x]],dfn[db[x]],dfn[x]);
		x=Tp[x];
		if (x==1) break;
		sg::upd(rt[ffa[x]],lfn[ffa[x]],rfn[ffa[x]],sfn[x]);
		x=ffa[x];
	}
}

int num_tours() 
{
	return CL::tr[rtc[1]].s012+CL::tr[rtc[1]].s210;
}