蚌埠住了

// Problem: P4074 [WC2013] 糖果公园
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4074
// Memory Limit: 500 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
int n,m,q;
const int N=1e5+10;
int v[N],w[N],c[N];
vector<int> g[N];
int a[N<<1],tot;
int l[N],r[N];
int FA[N][18],dep[N];
void dfs(int x,int fa,int dep=1){
	FA[x][0]=fa;
	::dep[x]=dep;
	l[x]=++tot;
	a[tot]=x;
	for(auto v:g[x]){
		if(v!=fa)dfs(v,x,dep+1);
	}
	r[x]=++tot;
	a[tot]=x;
}
void prefa(){
	rep(k,1,17)rep(i,1,n){
		FA[i][k]=FA[FA[i][k-1]][k-1];
	}
}
int lca(int u,int v){
	if(dep[u]>dep[v])swap(u,v);
	for(int i=17;i>=0;i--){
		if(dep[FA[v][i]]>=dep[u])v=FA[v][i];
	}
	if(u==v)return u;
	for(int i=17;i>=0;i--){
		if(FA[u][i]!=FA[v][i]){
			u=FA[u][i];
			v=FA[v][i];
		}
	}
	return FA[u][0];
}
struct oper{
	int x,y,w;
}ti[N];
int titt;
struct query{
	int l,r,t,id;
}qu[N];
int anss_wt[N];
int qutt;
int ans=0;
int cnt[N];
void add(int x){//type
	cnt[x]++;
	ans+=v[x]*w[cnt[x]];
}
void del(int x){
	ans-=v[x]*w[cnt[x]];
	cnt[x]--;
}
int bel[N<<2];
int vis[N],cc[N];
void operate(int pos){
	vis[a[pos]]^=1;
	if(vis[a[pos]]){
		add(c[a[pos]]);
	}else{
		del(c[a[pos]]);
	}
}
signed main(){
	cin>>n>>m>>q;
	rep(i,1,m)
		cin>>v[i];
	rep(i,1,n)
		cin>>w[i];
	rep(i,1,n-1){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);prefa();
	rep(i,1,n)
		cin>>c[i];
	rep(i,1,n)cc[i]=c[i];
	rep(i,1,q){
		int typ,x,y;
		cin>>typ>>x>>y;
		if(!typ){
			ti[++titt]={x,cc[x],y};cc[x]=y;
		}else{
			if(l[x]>l[y])swap(x,y);
			qu[++qutt]={r[x],l[y],titt,qutt};
		}
	}
	int B=pow(1.0*n*q,0.33);
	rep(i,1,n<<2){
		bel[i]=i/B+1;
	}
	sort(qu+1,qu+qutt+1,[](query a,query b){
		if(bel[a.l]==bel[b.l]){
			if(bel[a.r]==bel[b.r])return a.t<b.t;
			else return a.r<b.r;
		}else return a.l<b.l;
	});
	int l=1,r=0,t=0;
	rep(i,1,qutt){
		while(l>qu[i].l){//lca???
			l--;
			operate(l);
		}
		while(r>qu[i].r){
			operate(r);
			r--;
		}
		while(r<qu[i].r){
			r++;
			operate(r);
		}
		while(l<qu[i].l){
			operate(l);
			l++;
		}
		while(t<qu[i].t){
			t++;
			if(vis[ti[t].x]){
				operate(ti[t].y);
				operate(ti[t].w);
				c[ti[t].x]=ti[t].w;
			}
		}
		while(t>qu[i].t){
			if(vis[ti[t].x]){
				operate(ti[t].w);
				operate(ti[t].y);
				c[ti[t].x]=ti[t].y;
			}
			t--;
		}
		int lc=lca(a[l],a[r]);
		if(lc!=a[l]&&lc!=a[r]){
			add(c[lc]);
		}
		anss_wt[qu[i].id]=ans;
		del(c[lc]);
	}
	rep(i,1,qutt)cout<<anss_wt[i]<<'\n';
}