RT

问是我哪里写的比较炸嘛，为什么会T飞

#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
const int MAXN=1e5+10;
struct node
{
	int l,r,id,tim;
}qry[MAXN];
struct node1
{
	int p,x,y;
}chg[MAXN];
int totq,totc;
int in[MAXN],out[MAXN];
vector<int> g[MAXN];
int dfn[MAXN*2];
int totdfn;
int v[MAXN],c[MAXN],w[MAXN];
int vis[MAXN],sum;
int used[MAXN];
int ans[MAXN];
int l,r,Tim;
int n,m,q;
int len,bl[MAXN*2];
int sz[MAXN],son[MAXN],fa[MAXN];
int deep[MAXN],idx[MAXN],topfa[MAXN];
bool vised[MAXN];
int tot;
inline bool cmp(node a,node b)
{
	if(bl[in[a.l]]==bl[in[b.l]])
	{
		if(bl[in[a.r]]==bl[in[a.r]]) return a.tim<b.tim;
		return in[a.r]<in[b.r];
	}
	return in[a.l]<in[b.l];
}
void DFS1(int now,int lst)
{
	in[now]=++totdfn;
	dfn[totdfn]=now;
	for(int i=0;i<g[now].size();i++)
	{
		int v=g[now][i];
		if(v==lst) continue;
		DFS1(v,now);
	}
	out[now]=++totdfn;
	dfn[totdfn]=now;
}
void DFS2(int now,int lst,int depth)
{
	sz[now]=1;
	deep[now]=depth;
	fa[now]=lst;
	for(int i=0;i<g[now].size();i++)
	{
		int v=g[now][i];
		if(v==lst) continue;
		DFS2(v,now,depth+1);
		sz[now]+=sz[v];
		if(sz[v]>sz[son[now]]) son[now]=v;
	}
	return ;
}
void DFS3(int now,int lst,int top)
{
	if(now==0) return ;
	topfa[now]=top;
	idx[now]=++tot;
	vised[now]=true;
	DFS3(son[now],now,top);
	for(int i=0;i<g[now].size();i++)
	{
		int v=g[now][i];
		if(v==lst || vised[v]) continue;
		DFS3(v,now,v);
	}
	return ;
}
inline int LCA(int x,int y)
{
	while(topfa[x]!=topfa[y])
	{
		int fax=topfa[x],fay=topfa[y];
		if(deep[fay]>deep[fax])
		{
			swap(fax,fay);
			swap(x,y);
		}
		x=fa[fax];
	}
	if(deep[y]>deep[x]) swap(x,y);
	return y;
}
inline void doit(int t)
{
	while(Tim<t)
	{
		Tim++;
		c[chg[Tim].p]=chg[Tim].y;
		if(vis[chg[Tim].p]==1)
		{
			sum-=w[used[chg[Tim].x]]*v[chg[Tim].x];
			used[chg[Tim].x]--;
			used[chg[Tim].y]++;
			sum+=w[used[chg[Tim].y]]*v[chg[Tim].y];
		}
		
	}
	while(Tim>t)
	{
		
		c[chg[Tim].p]=chg[Tim].x;
		if(vis[chg[Tim].p]==1)
		{
			sum-=w[used[chg[Tim].y]]*v[chg[Tim].y];
			used[chg[Tim].y]--;
			used[chg[Tim].x]++;
			sum+=w[used[chg[Tim].x]]*v[chg[Tim].x];
		}
		Tim--;
	}
	return ;
}
inline void Del(int x)
{
//	cout<<"DEL::"<<x<<" ";
	if(vis[x]==1) 
	{
		sum-=w[used[c[x]]]*v[c[x]];
		used[c[x]]--;
	}
	vis[x]--;
	if(vis[x]==1)
	{
		used[c[x]]++;
		sum+=w[used[c[x]]]*v[c[x]];
	}
//	cout<<sum<<"\n";
	return ;
}
inline void Add(int x)
{
//	cout<<"ADD::"<<x<<" ";
	if(vis[x]==1)
	{
		sum-=w[used[c[x]]]*v[c[x]];
		used[c[x]]--;
	}
	vis[x]++;
	if(vis[x]==1)
	{
		used[c[x]]++;
		sum+=w[used[c[x]]]*v[c[x]];
	}
//	cout<<sum<<"\n";
	return ;
}
main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m>>q;
	len=pow(n*2,0.666);
	for(int i=1;i<=n*2;i++) bl[i]=(i-1)/len+1;
	for(int i=1;i<=m;i++) cin>>v[i];
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++) vis[i]=2;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==0)
		{
			int x,y;
			cin>>x>>y;
			chg[++totc].p=x;
			chg[totc].x=c[x];
			chg[totc].y=y;
			c[x]=y;
		}
		if(op==1)
		{
			int x,y;
			cin>>x>>y;
			qry[++totq].l=x;
			qry[totq].r=y;
			qry[totq].id=totq;
			qry[totq].tim=totc;
		}
	}
	DFS1(1,0);
	DFS2(1,0,1);
	DFS3(1,0,1);
	sort(qry+1,qry+1+totq,cmp);
	l=1,r=2*n,Tim=totc;
	for(int i=1;i<=totq;i++)
	{
		if(Tim!=qry[i].tim) doit(qry[i].tim);
		int L=in[qry[i].l],R=in[qry[i].r];
		if(L>R) swap(L,R),swap(qry[i].l,qry[i].r);
		while(l<L) Del(dfn[l++]);
		while(l>L) Add(dfn[--l]);
		while(r<R) Add(dfn[++r]);
		while(r>R) Del(dfn[r--]);
	//	cout<<sum<<'\n';
	//	cout<<l<<" "<<r<<"\n";
	//	cout<<sum<<" "<<c[2]<<"\n";
		int lca=LCA(qry[i].l,qry[i].r);
		ans[qry[i].id]=sum;
		if(qry[i].l!=lca) ans[qry[i].id]+=(w[used[c[qry[i].l]]+1])*v[c[qry[i].l]],used[c[qry[i].l]]++;
		if(lca!=qry[i].l && lca!=qry[i].r) ans[qry[i].id]+=(w[used[c[lca]]+1])*v[c[lca]];
		if(qry[i].l!=lca) used[c[qry[i].l]]--;
	}
	for(int i=1;i<=totq;i++) cout<<ans[i]<<"\n";
	return 0;
}