记录编号	458004	评测结果	AAAAAAAAAA
题目名称	[WC 2013] 糖果公园	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	19.154 s
提交时间	2017-10-09 21:48:10	内存使用	12.52 MiB

#include<bits/stdc++.h>
#define v e[i].to
#define ll long long
using namespace std;
const int ma=100005;
int n,m,Q,fi[ma],tot,w[ma],dfn[ma<<1],cnt[ma],h[ma],c[ma],ans[ma],pos[ma<<1],o1,o2,st[ma],ed[ma],temp[ma];
int siz[ma],top[ma],fa[ma],son[ma],dep[ma];
struct edge{
	int to,next;
}e[ma<<1];
void edge_add(int x,int y){
	e[++tot].to=y;
	e[tot].next=fi[x];
	fi[x]=tot;
}
struct Ques{
	int l,r,tim,id,lc;ll ans;
	bool operator < (const Ques&o)const{
		if(pos[l]!=pos[o.l])return l<o.l;
		if(pos[r]!=pos[o.r])return r<o.r;
		return tim<o.tim;
	}
}q[ma];
struct Change{
	int id,from,to;
}change[ma];
void dfs1(int x){
	dfn[++tot]=x;st[x]=tot;
	for(int i=fi[x];i;i=e[i].next){
		if(fa[x]==v)continue;
		fa[v]=x;dep[v]=dep[x]+1;
		dfs1(v);siz[x]+=siz[v];
		if(siz[v]>siz[son[x]])son[x]=v;
	}dfn[++tot]=x;ed[x]=tot;
}
void dfs2(int x,int y){
	top[x]=y;
	if(son[x])dfs2(son[x],y);
	for(int i=fi[x];i;i=e[i].next){
		if(top[v])continue;
		dfs2(v,v);
	}
}
int get_lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}return dep[x]<dep[y]?x:y;
}
bool cmp(Ques x,Ques y){
	return x.id<y.id;
}
int read(){
	char ch=getchar();
	int a=0;
	while(!(ch<='9'&&ch>='0'))ch=getchar();
	while(ch<='9'&&ch>='0'){
		a=(a<<1)+(a<<3)+('0'^ch);
		ch=getchar();
	}return a;
}
int main()
{
	int __size__ = 128<<20;
	char *__ptr__ = (char *)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__ptr__));
	freopen("park.in","r",stdin);freopen("park.out","w",stdout);
	n=read(),m=read(),Q=read();
	for(int i=1;i<=m;i++)h[i]=read();
	for(int i=1;i<=n;i++)w[i]=read();
	for(int i=1;i<n;i++){
		int x,y;x=read();y=read();
		edge_add(x,y);edge_add(y,x);
	}tot=0;
	for(int i=1;i<=n;i++)c[i]=read(),temp[i]=c[i],siz[i]=1;
	dfs1(1);dfs2(1,1);
	int len=5000;
	for(int i=1;i<=tot;i++)pos[i]=(i-1)/len+1;
	for(int i=1;i<=Q;i++){
		int t,x,y;t=read();x=read();y=read();
		if(t){
			if(st[x]>st[y])swap(x,y);
			int lc=get_lca(x,y);q[++o1].id=o1;
			if(lc!=x)q[o1].l=ed[x],q[o1].r=st[y],q[o1].tim=o2,q[o1].lc=lc;
			else q[o1].l=st[x],q[o1].r=st[y],q[o1].tim=o2;
		}
		else{
			change[++o2].id=x;change[o2].from=temp[x];change[o2].to=y;temp[x]=y;
		}
	}sort(q+1,q+o1+1);
	int l=1,r=0,t=0;ll now=0;
	for(int i=1;i<=o1;i++){
		while(t<q[i].tim){
			t++;
			if(cnt[change[t].id]&1){
				++ans[change[t].to];
				now+=(ll)w[ans[change[t].to]]*(ll)h[change[t].to];
				now-=(ll)w[ans[change[t].from]]*(ll)h[change[t].from];
				ans[change[t].from]--;
			}c[change[t].id]=change[t].to;
		}
		while(t>q[i].tim){
			if(cnt[change[t].id]&1){
				++ans[change[t].from];
				now+=(ll)w[ans[change[t].from]]*(ll)h[change[t].from];
				now-=(ll)w[ans[change[t].to]]*(ll)h[change[t].to];
				ans[change[t].to]--;
			}c[change[t].id]=change[t].from;t--;
		}
		while(l<q[i].l){
			cnt[dfn[l]]--;
			if(cnt[dfn[l]]&1)ans[c[dfn[l]]]++,now+=(ll)w[ans[c[dfn[l]]]]*(ll)h[c[dfn[l]]];
			else now-=(ll)w[ans[c[dfn[l]]]]*(ll)h[c[dfn[l]]],ans[c[dfn[l]]]--;
			l++;
		}
		while(l>q[i].l){
			l--;cnt[dfn[l]]++;
			if(cnt[dfn[l]]&1)ans[c[dfn[l]]]++,now+=(ll)w[ans[c[dfn[l]]]]*(ll)h[c[dfn[l]]];
			else now-=(ll)w[ans[c[dfn[l]]]]*(ll)h[c[dfn[l]]],ans[c[dfn[l]]]--;
		}
		while(r<q[i].r){
			r++;cnt[dfn[r]]++;
			if(cnt[dfn[r]]&1)ans[c[dfn[r]]]++,now+=(ll)w[ans[c[dfn[r]]]]*(ll)h[c[dfn[r]]];
			else now-=(ll)w[ans[c[dfn[r]]]]*(ll)h[c[dfn[r]]],ans[c[dfn[r]]]--;
		}
		while(r>q[i].r){
			cnt[dfn[r]]--;
			if(cnt[dfn[r]]&1)ans[c[dfn[r]]]++,now+=(ll)w[ans[c[dfn[r]]]]*(ll)h[c[dfn[r]]];
			else now-=(ll)w[ans[c[dfn[r]]]]*(ll)h[c[dfn[r]]],ans[c[dfn[r]]]--;
			r--;
		}
		q[i].ans=now+(ll)h[c[q[i].lc]]*(ll)w[ans[c[q[i].lc]]+1];
	}
	sort(q+1,q+o1+1,cmp);
	for(int i=1;i<=o1;i++)printf("%lld\n",q[i].ans);
	return 0;
}