#include "joitour.h"
#include<bits/stdc++.h>

#define ll long long
#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;

mt19937 gen(time(0));

const int N = 2e5 + 5;

int n, a[N];
ll c0, c2, sum, sum0, sum2, f[N], g[N];
int le[N], ri[N], fa[N], dep[N], sz[N], top[N], son[N], dfn[N], idf[N], DFN;
vc <int> G[N];

struct bit {
	int tre[N];
	inline int lb (int x) { return x & - x; }
	inline void add (int p, int v) { while (p <= n) tre[p] += v, p += lb (p); }
	inline int ask (int p) { int res = 0; while (p) res += tre[p], p -= lb (p); return res; }
	inline ll sz (int x) { return x ? ask (ri[x]) - ask (le[x] - 1) : 0; }
	inline void clear () { rep (i, 0, n) tre[i] = 0; }
} C0, C2, S0, S2;

namespace sgt {
	ll t0[N << 2], t2[N << 2], cnt[N << 2], ad0[N << 2], ad2[N << 2];
	#define mid (l + r >> 1)
	#define ls (k << 1)
	#define rs (k << 1 | 1)
	inline void psu (int k) {
		t0[k] = t0[ls] + t0[rs];
		t2[k] = t2[ls] + t2[rs];
		cnt[k] = cnt[ls] + cnt[rs];  
	}
	inline void ps (int k, int a0, int a2) {
		t0[k] += a0 * cnt[k]; ad0[k] += a0; 
		t2[k] += a2 * cnt[k]; ad2[k] += a2;
	}
	inline void psd (int k) {
		if (ad0[k] || ad2[k]) 
			ps (ls, ad0[k], ad2[k]), ps (rs, ad0[k], ad2[k]);
		ad0[k] = ad2[k] = 0;
	}
	inline void ins (int k, int l, int r, int p, ll v0, ll v2, ll v) {
		// if (p == dfn[2]) cerr << "sgt " << v0 << " " << v2 << " " << v << endl;
		if (l == r) return t0[k] += v * v0, t2[k] += v * v2, cnt[k] += v, void (); psd (k);
		return (p <= mid ? ins (ls, l, mid, p, v0, v2, v) : ins (rs, mid + 1, r, p, v0, v2, v)), psu (k);
	}
	inline void modify (int k, int l, int r, int L, int R, ll v0, ll v2) {
		if (L > R || L > r || R < l) return ;
		if (L <= l && R >= r) return ps (k, v0, v2); psd (k);
		modify (ls, l, mid, L, R, v0, v2); modify (rs, mid + 1, r, L, R, v0, v2); psd (k);
	}
	inline ll ask0 (int k, int l, int r, int L, int R) {
		if (L > R || L > r || R < l) return 0;
		if (L <= l && R >= r) return t0[k]; psd (k);
		return ask0 (ls, l, mid, L, R) + ask0 (rs, mid + 1, r, L, R);
	}
	inline ll ask2 (int k, int l, int r, int L, int R) {
		if (L > R || L > r || R < l) return 0;
		if (L <= l && R >= r) return t2[k]; psd (k);
		return ask2 (ls, l, mid, L, R) + ask2 (rs, mid + 1, r, L, R);
	}
	#undef mid
	#undef ls
	#undef rs
}
using namespace sgt;

inline void add0 (int x, int v) {
	c0 += v; sum0 += v * S0.ask (dfn[x]); C0.add (dfn[x], v);
	for (; x; x = fa[x]) {
		sum += v * ask2 (1, 1, n, dfn[top[x]], dfn[x]);
		modify (1, 1, n, dfn[top[x]], dfn[x], v, 0);
		if (a[fa[x = top[x]]] == 1) sum -= g[x]; 
		f[fa[x]] -= g[x]; g[x] = C0.sz (x) * C2.sz (x); f[fa[x]] += g[x];
		if (a[fa[x]] == 1) sum += g[x]; 
	}
}

inline void add2 (int x, int v) {
	c2 += v; sum2 += v * S2.ask (dfn[x]); C2.add (dfn[x], v);
	for (; x; x = fa[x]) {
		sum += v * ask0 (1, 1, n, dfn[top[x]], dfn[x]);
		modify (1, 1, n, dfn[top[x]], dfn[x], 0, v);
		if (a[fa[x = top[x]]] == 1) sum -= g[x]; 
		f[fa[x]] -= g[x]; g[x] = C0.sz (x) * C2.sz (x); f[fa[x]] += g[x];
		if (a[fa[x]] == 1) sum += g[x]; 
	}
}

inline void add1 (int x, int v) {
	S0.add (le[x], v); S0.add (ri[x] + 1, - v);
	S2.add (le[x], v); S2.add (ri[x] + 1, - v);
	sum += v * ( C0.sz (x) * C2.sz (x) + C0.sz (son[x]) * C2.sz (son[x]) + f[x] );
	sum0 += v * C0.sz (x);
	sum2 += v * C2.sz (x);
	// if (x == 2) cerr << v << " " << C0.sz (x) << " " << C2.sz (x) << endl;
	ins (1, 1, n, dfn[x], C0.sz (x), C2.sz (x), v);
	// cerr << "debug " << ask0 (1, 1, n, dfn[2], dfn[2]) << endl;
	if (son[x]) ins (1, 1, n, dfn[x] + 1, C0.sz (son[x]), C2.sz (son[x]), v);
}

inline void dfs1 (int x) {
	sz[x] = 1;
	for (auto y : G[x]) if (y != fa[x]) {
		fa[y] = x; dep[y] = dep[x] + 1; dfs1 (y); sz[x] += sz[y];
		son[x] = sz[y] > sz[son[x]] ? y : son[x]; 
	}
}

inline void dfs2 (int x, int t) {
	top[x] = t; dfn[x] = le[x] = ++ DFN; idf[DFN] = x;
	if (son[x]) dfs2 (son[x], t);
	for (auto y : G[x]) if (y != fa[x] && y != son[x]) dfs2 (y, y);
	ri[x] = DFN;
}

inline void dfs (int x) {
	for (auto y : G[x]) if (y != fa[x]) {
		dfs (y); 
		if (y != son[x]) f[x] += (g[y] = C0.sz (y) * C2.sz (y));
	}
	if (a[x] == 1) add1 (x, 1);
}

void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) {
	n = N;
	rep (i, 1, n) a[i] = F[i - 1];
	
	auto add = [&] (int x, int y) { G[x].pb (y); G[y].pb (x); } ;
	rep (i, 0, n - 2) add (U[i] + 1, V[i] + 1);
	
	dep[1] = 1; dfs1 (1); dfs2 (1, 1);
	rep (i, 1, n) 
		if (a[i] == 0) ++ c0, C0.add (dfn[i], 1);
		else if (a[i] == 2) ++ c2, C2.add (dfn[i], 1);
	dfs (1);
		
	// cerr << "init finished    " << sum << endl;	
}

void change(int X, int Y) {
	// cerr << "debug " << ask0 (1, 1, n, dfn[2], dfn[2]) << endl;
	int x = ++ X;
	if (a[x] == 0) add0 (x, - 1);
	if (a[x] == 1) add1 (x, - 1);
	if (a[x] == 2) add2 (x, - 1);
	a[x] = Y;
	if (a[x] == 0) add0 (x, 1);
	if (a[x] == 1) add1 (x, 1);
	if (a[x] == 2) add2 (x, 1);
}

long long num_tours() {
	// cerr << c0 << " " << c2 << " " << sum0 << " " << sum2 << " " << sum << endl;
	return c0 * sum2 + c2 * sum0 - sum;	
}