rt,过不了样例

#include <bits/stdc++.h>
using namespace std;
int n,m,q,opt,v[100005],dep[100005],tim,f[100005][20],tre,lst[100005],pos[100005],nxt[100005],w[100005],cnt[100005],
a[100005],b[100005],tr[200005],fst[100005],sec[100005],bl[200005],c[100005],block,x,y;
long long now,ans[100005];
vector<int> g[100005];
bitset<100005> vis;
struct qr{
	int l,r,id,t,lc;
	bool operator <(qr x) const{
		return bl[l]^bl[x.l]?l<x.l:r^x.r?r<x.r:t<x.t;
	}
}qu[100005];
void dfs(int x,int fa){
	fst[x]=++tre,tr[tre]=x,dep[x]=dep[fa]+1,f[x][0]=fa;
	for(int i=1;i<=(int)log2(dep[x]);i++)
		f[x][i]=f[f[x][i-1]][i-1];
	for(int i=0;i<g[x].size();i++)
		if(g[x][i]^fa)
			dfs(g[x][i],x);
	sec[x]=++tre,tr[tre]=x;
}
inline int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]) x=f[x][(int)log2(dep[x]-dep[y])];
	if(x==y) return x;
	for(int i=(int)log2(dep[x]);~i;i--)
		if(f[x][i]^f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline void dl(int x){
	now-=1ll*w[cnt[c[x]]]*v[c[x]];
	cnt[c[x]]--;
}
inline void ad(int x){
	cnt[c[x]]++;
	now+=1ll*w[cnt[c[x]]]*v[c[x]];	
}
inline void Add(int x){
	if(vis[tr[x]]){
		vis[tr[x]]=0;
		dl(tr[x]);
	}
	else ad(tr[x]),vis[tr[x]]=1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q,block=pow(n<<1,0.66);
	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++)
		cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
	for(int i=1;i<=n;i++)
		cin>>a[i],b[i]=c[i]=a[i];
	for(int i=1;i<=q;i++){
		cin>>opt;
		if(opt) cin>>qu[i-tim].l>>qu[i-tim].r,qu[i-tim].t=tim,qu[i-tim].id=i-tim;
		else cin>>x>>y,lst[++tim]=b[x],b[x]=nxt[tim]=y,pos[tim]=x;
	}
	dfs(1,0);
	for(int i=1;i<=q-tim;i++){
		if(fst[qu[i].l]>fst[qu[i].r]) swap(qu[i].l,qu[i].r);
		if(sec[qu[i].l]>sec[qu[i].r]) qu[i].l=fst[qu[i].l],qu[i].r=fst[qu[i].r],qu[i].lc=-114;
		else qu[i].lc=lca(qu[i].l,qu[i].r),qu[i].l=sec[qu[i].l],qu[i].r=fst[qu[i].r];
//		if(qu[i].l>qu[i].r) swap(qu[i].l,qu[i].r);
//		cout<<qu[i].lc<<'\n';
	}
//	for(int i=1;i<=n;i++)
//		cout<<fst[i]<<' '<<sec[i]<<'\n';
	for(int i=1;i<=(n<<1);i++)
		bl[i]=(i-1)/block+1;
	sort(qu+1,qu+q-tim+1);
	for(int i=1,lt=1,rt=0,tt=0;i<=q-tim;i++){
		while(lt>qu[i].l) Add(--lt);
		while(rt<qu[i].r) Add(++rt);
		while(lt<qu[i].l) Add(lt++);
		while(rt>qu[i].r) Add(rt--);
		while(tt<qu[i].t){
			tt++;
			c[pos[tt]]=nxt[tt];
//			if(lt<=fst[pos[tt]]&&fst[pos[tt]]<=rt) vis[nxt[tt]]=!vis[nxt[tt]],vis[lst[tt]]=!vis[lst[tt]];
//			if(lt<=sec[pos[tt]]&&sec[pos[tt]]<=rt) vis[nxt[tt]]=!vis[nxt[tt]],vis[lst[tt]]=!vis[lst[tt]];
			if((lt<=fst[pos[tt]]&&fst[pos[tt]]<=rt&&(lt>sec[pos[tt]]||rt<sec[pos[tt]]))
			||(lt<=sec[pos[tt]]&&sec[pos[tt]]<=rt&&(lt>fst[pos[tt]]||rt<fst[pos[tt]])))
				now-=1ll*v[lst[tt]]*w[cnt[lst[tt]]],cnt[lst[tt]]--,cnt[nxt[tt]]++,now+=1ll*v[nxt[tt]]*w[cnt[nxt[tt]]];
		}
		while(tt>qu[i].t){
			c[pos[tt]]=lst[tt];
//			if(lt<=fst[pos[tt]]&&fst[pos[tt]]<=rt) vis[nxt[tt]]=!vis[nxt[tt]],vis[lst[tt]]=!vis[lst[tt]];
//			if(lt<=sec[pos[tt]]&&sec[pos[tt]]<=rt) vis[nxt[tt]]=!vis[nxt[tt]],vis[lst[tt]]=!vis[lst[tt]];
			if((lt<=fst[pos[tt]]&&fst[pos[tt]]<=rt&&(lt>sec[pos[tt]]||rt<sec[pos[tt]]))
			||(lt<=sec[pos[tt]]&&sec[pos[tt]]<=rt&&(lt>fst[pos[tt]]||rt<fst[pos[tt]])))
				now-=1ll*v[nxt[tt]]*w[cnt[nxt[tt]]],cnt[nxt[tt]]--,cnt[lst[tt]]++,now+=1ll*v[lst[tt]]*w[cnt[lst[tt]]];
			tt--;
		}
		if(qu[i].lc^-114){
			if(vis[qu[i].lc]){
				vis[qu[i].lc]=0;
				dl(qu[i].lc);
			}
			else ad(qu[i].lc),vis[qu[i].lc]=1;
		}
		ans[qu[i].id]=now;
	}
	for(int i=1;i<=q-tim;i++)
		cout<<ans[i]<<'\n';
	return 0;
}
/*
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2
*/