记录编号	483227	评测结果	AAAAAAAAAA
题目名称	[WC 2013] 糖果公园	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	12.706 s
提交时间	2018-01-15 19:35:55	内存使用	30.26 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m,q_cnt,v[N],w[N],c[N];
int q[N],L[N],R[N],size;
int block_size,now,p[N],fr[N],to[N],cnt_query;
struct query{int l,r,T,lca;}Q[N];
namespace init{
	int e[N],nxt[N],head[N];
	void add(int f,int t){
		static int cnt=0;
		e[++cnt]=t;
		nxt[cnt]=head[f];
		head[f]=cnt;
	}
	int dep[N],dp[18][N];
	void dfs(int x){
		q[L[x]=++size]=x;
		for (int i=head[x];i;i=nxt[i])
		if (!L[e[i]]) dep[e[i]]=dep[x]+1,dp[0][e[i]]=x,dfs(e[i]);
		q[R[x]=++size]=x;
	}
	int lca(int x,int y){
		if (dep[x]<dep[y]) swap(x,y);
		for (int D=dep[x]-dep[y],i=0;i<18;i++)
		if (D>>i&1) x=dp[i][x];
		for (int i=17;i>=0;i--)
		if (dp[i][x]!=dp[i][y]) x=dp[i][x],y=dp[i][y];
		return x==y?x:dp[0][x];
	}
	void init(){
		scanf("%d%d%d",&n,&m,&q_cnt);
		block_size=pow(n,0.67);
		for (int i=1;i<=m;i++) scanf("%d",&v[i]);
		for (int i=1;i<=n;i++) scanf("%d",&w[i]);
		for (int i=1;i<n;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v);add(v,u);
		}
		dep[1]=1;dfs(1);
		for (int i=1;i<18;i++)
		for (int j=1;j<=n;j++)
			dp[i][j]=dp[i-1][dp[i-1][j]];
		for (int i=1;i<=n;i++) scanf("%d",&c[i]);
		static int now[N];
		for (int i=1;i<=n;i++) now[i]=c[i];
		for (int i=1;i<=q_cnt;i++){
			int tp,x,y;
			scanf("%d%d%d",&tp,&x,&y);
			if (tp){
				if (L[x]>L[y]) swap(x,y);
				if (R[x]<L[y])
					Q[++cnt_query]=(query){R[x],L[y],i,lca(x,y)};
				else
					Q[++cnt_query]=(query){L[x],L[y],i,0};
			}
			else p[i]=x,fr[i]=now[x],to[i]=now[x]=y;
		}
	}
}
int cnt[N];bool ins[N];ll ans;
bool cmp(query x,query y){
	if (x.l/block_size!=y.l/block_size) return x.l<y.l;
	if (x.r/block_size!=y.r/block_size) return x.r<y.r;
	return x.T<y.T;
}
void insert(int c){ans+=(ll)w[++cnt[c]]*v[c];}
void erase(int c){ans-=(ll)w[cnt[c]--]*v[c];}
void _insert(int x){(ins[x]=!ins[x])?insert(c[x]):erase(c[x]);}
void jump(int T){
	while (now<T){
		++now;
		if (ins[p[now]]) erase(fr[now]),insert(to[now]);
		c[p[now]]=to[now];
	}
	while (now>T){
		if (ins[p[now]]) erase(to[now]),insert(fr[now]);
		c[p[now]]=fr[now];
		now--;
	}
}
ll Ans[N];
int main()
{
	freopen("park.in","r",stdin);
	freopen("park.out","w",stdout);
	init::init();
	sort(Q+1,Q+cnt_query+1,cmp);
	int l=1,r=0;
	for (int i=1;i<=cnt_query;i++){
		int L=Q[i].l,R=Q[i].r;
		while (r<R) _insert(q[++r]);
		while (l>L) _insert(q[--l]);
		while (r>R) _insert(q[r--]);
		while (l<L) _insert(q[l++]);
		if (Q[i].lca) _insert(Q[i].lca);
		jump(Q[i].T);
		Ans[Q[i].T]=ans;
		if (Q[i].lca) _insert(Q[i].lca);
	}
	for (int i=1;i<=q_cnt;i++)
	if (Ans[i]) printf("%lld\n",Ans[i]);
	return 0;
}