TLE

我应该不是常数问题

因为我只需要注释掉莫队中的 q[q[i].id].res=ans 他就是wa了，我真的要死了。

所以应该不需要卡常的技巧（Fastio依旧 TLE

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include <bits/stdc++.h>
#define lb(x) (x&-x)

using namespace std;
using i64 = long long;

const int maxn = 2e5 + 10, mod = 998244353;
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x,int c){x=min(x,c);}
void chmax(int &x,int c){x=max(x,c);}

int h[maxn],e[maxn],ne[maxn],idx;
int in[maxn],out[maxn],pos[maxn],fa[maxn],d[maxn],top[maxn],son[maxn],sz[maxn],dfn;
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int p,int dep){
	fa[u]=p,d[u]=dep,in[u]=++dfn;
	pos[dfn]=u,sz[u]=1,son[u]=-1;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==p)continue;
		dfs(v,u,dep+1),sz[u]+=sz[v];
		if(son[u]==-1||sz[v]>sz[son[u]])son[u]=v;
	}
	out[u]=++dfn,pos[dfn]=u;
} 
void dfs(int u,int p){
	top[u]=p;
	if(son[u]==-1)return;
	dfs(son[u],p);
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if((j^fa[u])&&(j^son[u]))dfs(j,j);
	}
}
int LCA(int x,int y){
	while(top[x]^top[y]){
		if(d[top[x]]<d[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return d[x]<d[y]?x:y;
}
struct qwq{
	int l,r,id,lca,t,res;
}q[maxn];
struct qaq{
	int p,d;
}c[maxn];
int n,m,a[maxn],ccnt=0,qcnt=0,B,cnt[maxn];
ll ans;
bool st[maxn];
inline bool cmp(const qwq &QwQ,const qwq &QaQ){
	return (QwQ.l/B==QaQ.l/B?(QwQ.r/B==QaQ.r/B?\
	QwQ.t<QaQ.t:QwQ.r<QaQ.r):QwQ.l<QaQ.r);
}
void del(int x){
	ans-=(ll)cnt[x]-1;
	cnt[x]--;
}
void add(int x){
	ans+=(ll)cnt[x];
	cnt[x]++;
}
void upd2(int x){
	if(st[x])del(a[x]);
	else add(a[x]);
	st[x]^=1;
}
void upd(int x){
	if(st[c[x].p])del(a[c[x].p]),add(c[x].d);
	swap(a[c[x].p],c[x].d); 
}

void solve(){
	ios::sync_with_stdio(false);
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v,u++,v++;
		add(u,v),add(v,u);
	}
	dfs(1,0,1),dfs(1,1);
//	for(int i=1;i<=n;i++){
//		cout<<top[i]<<' '<<son[i]<<'\n';
//	}
	for(int i=1;i<=m;i++){
		int opt,a,b;
		cin>>opt>>a>>b;
		if(opt==1)a++,ccnt++,c[ccnt].p=a,c[ccnt].d=b;
		else{
			a++,b++,qcnt++;
			if(in[a]>in[b])swap(a,b);
			int lca=LCA(a,b);
			if(lca==a){
				q[qcnt].l=in[a],q[qcnt].r=in[b],q[qcnt].lca=0\
				,q[qcnt].id=qcnt,q[qcnt].t=ccnt;
			}else{
				q[qcnt].l=out[a],q[qcnt].r=in[b],q[qcnt].lca=lca\
				,q[qcnt].id=qcnt,q[qcnt].t=ccnt;
			}
		}
	}
//	for(int i=1;i<=qcnt;i++){
//		cout<<q[i].l<<' '<<q[i].r<<' '<<q[i].lca<<' '<<q[i].id<<' '<<q[i].t<<'\n';
//	}
	B=pow(2*n,2.0/3);
	sort(q+1,q+1+qcnt,cmp);
//	for(int i=1;i<=qcnt;i++){
//		cout<<q[i].l<<' '<<q[i].r<<' '<<q[i].lca<<' '<<q[i].id<<' '<<q[i].t<<'\n';
//	}	
	int l=1,r=0,t=0;
	for(int i=1;i<=qcnt;i++){	
		int ql=q[i].l,qr=q[i].r,qt=q[i].t,qlca=q[i].lca;
		while(l<ql)upd2(pos[l++]);
		while(l>ql)upd2(pos[--l]);
		while(r<qr)upd2(pos[++r]);
		while(r>qr)upd2(pos[r--]);
		while(t<qt)upd(++t);
		while(t>qt)upd(t--);
		if(qlca)upd2(qlca);
//		cout<<ans<<'\n';
		q[q[i].id].res=ans;
		if(qlca)upd2(qlca);
	}
	for(int i=1;i<=qcnt;i++){
		cout<<(q[i].res)<<'\n';
	}
}

signed main() {
  int T=1;
  while(T--)solve();
  return 0;
}