RT

真查不出来哪里出错了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=5e5+5;
ll n,q,op,x,y,blen,now_lca; 
ll a[MAXN];
struct query{
	ll id,t,l,r,w;
	bool operator < (const query &oth)const{
		return l/blen==oth.l/blen?(r/blen==oth.r/blen?t<oth.t:r/blen<oth.r/blen):l/blen<oth.l/blen;
	}
}Q[MAXN];
struct update{
	ll pos,col;
}R[MAXN];
ll qcnt,rcnt;
struct edge{
	ll u,v,nxt;
}e[MAXN];
ll head[MAXN],edge_num;
void add_edge(ll From,ll To){
	edge_num++;
	e[edge_num].u=From;
	e[edge_num].v=To;
	e[edge_num].nxt=head[From];
	head[From]=edge_num;
	return;
}
ll fa[MAXN][35],deep[MAXN];
ll rk[MAXN],now_time,pos1[MAXN],pos2[MAXN];
void pre(ll now,ll father){
	deep[now]=deep[father]+1;
	fa[now][0]=father;
	rk[++now_time]=now;
	pos1[now]=now_time;
	for(int i=1;i<=30;i++)fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].v==father)continue;
		pre(e[i].v,now);
	}
	rk[++now_time]=now;
	pos2[now]=now_time;
	return;
}
ll LCA(ll X,ll Y){
	if(deep[X]<deep[Y])swap(X,Y);
	for(int i=30;i>=0&&deep[X]!=deep[Y];i--)if(deep[fa[X][i]]>=deep[Y])X=fa[X][i];
	if(X==Y)return X;
	for(int i=30;i>=0;i--)if(fa[X][i]!=fa[Y][i])X=fa[X][i],Y=fa[Y][i];
	return fa[X][0]; 
}
ll cnt[MAXN];
ll res;
ll ans[MAXN];
bool vis[MAXN];
void add(ll X){
	res-=(1ll*cnt[X]*(cnt[X]-1)/2);
	cnt[X]++;
	res+=(1ll*cnt[X]*(cnt[X]-1)/2);
	return;
}
void del(ll X){
	res-=(1ll*cnt[X]*(cnt[X]-1)/2);
	cnt[X]--;
	res+=(1ll*cnt[X]*(cnt[X]-1)/2);
	return;
}
void opt(ll X){
	if(!vis[X])add(a[X]);
	else del(a[X]);
	vis[X]^=1;
//	cout<<res<<endl;
	return;
}
void change(ll X){
	if(vis[X]){
		del(a[R[X].pos]);
		add(R[X].col);
	}
	swap(a[R[X].pos],R[X].col);
	return;
}
int main(){
	cin>>n>>q;
	blen=pow(2*n,2.0/3.0);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		cin>>x>>y;
		add_edge(x+1,y+1);
		add_edge(y+1,x+1);
	}
	pre(1,1);
	for(int i=1;i<=q;i++){
		cin>>op;
		if(op==1){
			cin>>x>>y;
			x++;
			R[++rcnt]=(update){x,y};
		}
		else{
			cin>>x>>y;
			x++,y++;
			qcnt++;
			if(pos1[x]>pos1[y])swap(x,y);
			now_lca=LCA(x,y);
			if(now_lca==x)Q[qcnt]=(query){qcnt,rcnt,pos1[x],pos1[y],0};
			else Q[qcnt]=(query){qcnt,rcnt,pos2[x],pos1[y],now_lca};
		} 
	}
	sort(Q+1,Q+1+qcnt);
	ll _l=1,_r=0,_t=0;
	for(int i=1;i<=qcnt;i++){
//		cout<<"case "<<i<<'\n';
		while(_l<Q[i].l)opt(rk[_l++]);
		while(_l>Q[i].l)opt(rk[--_l]);
		while(_r<Q[i].r)opt(rk[++_r]);
		while(_r>Q[i].r)opt(rk[_r--]);
		while(_t>Q[i].t)change(_t--);
		while(_t<Q[i].t)change(++_t);
		if(Q[i].w)opt(Q[i].w);
		ans[Q[i].id]=res;
		if(Q[i].w)opt(Q[i].w);
	}
	for(int i=1;i<=qcnt;i++)cout<<ans[i]<<'\n';
	return 0;
}