记录编号	155273	评测结果	AAAAAAAAAA
题目名称	[WC 2013] 糖果公园	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	19.785 s
提交时间	2015-03-28 08:40:33	内存使用	20.23 MiB

#include<cmath>
#include<cstdio>
#include<algorithm>
typedef long long lnt;
const int maxn=100010,maxm=200010;
bool vis[maxn];
lnt ansnow,ans[maxn];
char ch[10000000],*ptr=ch;
int n,m,z,v[maxn],w[maxn],cnt[maxn],col[maxn],last[maxn];
int len,sizen,cntblc,g[maxn],to[maxm],bel[maxn],next[maxm];
int fa[maxn],sta[maxn],siz[maxn],son[maxn],dep[maxn],top[maxn];
struct node{
	int u,v,id,tim;
}q1[maxn],q2[maxn];
void swap(int &x,int &y){
	x^=y,y^=x,x^=y;
}
void ins(int u,int v){
	to[++len]=v,next[len]=g[u],g[u]=len;
}
void in(int &x){
    x=0;
    while(*ptr<48) ptr++;
    while(*ptr>47) x=x*10+*ptr++-48;
}
void update(int x){
	if(vis[x]) ansnow-=(lnt)v[col[x]]*w[cnt[col[x]]--];
	else ansnow+=(lnt)v[col[x]]*w[++cnt[col[x]]];
	vis[x]^=1;
}
void modify(int u,int v){
	if(vis[u]) update(u),col[u]=v,update(u);
	else col[u]=v;
}
void moveto(int u,int v){
	while(u!=v)
		if(dep[u]>dep[v]) update(u),u=fa[u];
		else update(v),v=fa[v];
}
bool cmp(node a,node b){
	if(bel[a.u]!=bel[b.u]) return bel[a.u]<bel[b.u];
	if(bel[a.v]!=bel[b.v]) return bel[a.v]<bel[b.v];
	return a.id<b.id;
}
void getans(int i,int u){
	update(u);
	ans[q1[i].id]=ansnow;
	update(u);
}
int lca(int u,int v){
	for(int fu=top[u],fv=top[v];fu!=fv;u=fa[fu],fu=top[u])
		if(dep[fu]<dep[fv]) swap(fu,fv),swap(u,v);
	if(dep[u]<dep[v]) return u;
	return v;
}
void dfs(int x){
	sta[++sta[0]]=x;
	for(int p,i=g[x];i;i=next[i]){
		if((p=to[i])==fa[x]) continue;
		dfs(p),siz[x]+=siz[p];
		if(siz[x]>sizen){
			siz[x]=0,cntblc++;
			while(sta[sta[0]]!=x) bel[sta[sta[0]--]]=cntblc;
		}
	}
	siz[x]++;
}
void init(){
	int i,u,vv,x,p;
	in(n),in(m),in(z),sizen=(int)pow(n,2.0/3.0)*.5;
	for(i=1;i<=m;i++) in(v[i]);
	for(i=1;i<=n;i++) in(w[i]);
	for(i=1;i<n;i++) in(u),in(vv),ins(u,vv),ins(vv,u);
	for(i=1;i<=n;i++) in(col[i]),last[i]=col[i];
	u=1,vv=1,sta[1]=1;
	while(u<=vv){
		x=sta[u++],siz[x]=1;
		for(i=g[x];i;i=next[i])
			if((p=to[i])!=fa[x])
				dep[p]=dep[x]+1,fa[p]=x,sta[++vv]=p;
	}
	for(i=n;i;i--){
		x=sta[i],siz[fa[x]]+=siz[x];
		if(siz[x]>siz[son[fa[x]]]) son[fa[x]]=x;
	}
	for(i=1;i<=n;i++){
		x=sta[i],siz[x]=0;
		if(son[fa[x]]==x) top[x]=top[fa[x]];
		else for(top[x]=x;x;x=son[x]);
	}
	dfs(1),cntblc++;
	while(sta[0]) bel[sta[sta[0]--]]=cntblc;
}
void work(){
	int i,u,vv,cmd,totq=0,totc=0,timnow=1;
	for(i=1;i<=z;i++){
		in(cmd),in(u),in(vv);
		if(cmd){
			totq++;
			if(bel[u]>bel[vv]) swap(u,vv);
			q1[totq]=(node){u,vv,totq,totc};
		}
		else q2[++totc].id=u,q2[totc].u=last[u],q2[totc].v=last[u]=vv;
	}
	std::sort(q1+1,q1+totq+1,cmp);
	while(timnow<=q1[1].tim) modify(q2[timnow].id,q2[timnow].v),timnow++;
	moveto(q1[1].u,q1[1].v),getans(1,lca(q1[1].u,q1[1].v));
	for(i=2;i<=totq;i++){
		while(timnow<=q1[i].tim) modify(q2[timnow].id,q2[timnow].v),timnow++;
		while(timnow>q1[i].tim+1)modify(q2[timnow-1].id,q2[timnow-1].u),timnow--;
		moveto(q1[i-1].u,q1[i].u),moveto(q1[i-1].v,q1[i].v),getans(i,lca(q1[i].u,q1[i].v));
	}
	for(i=1;i<=totq;i++) printf("%lld\n",ans[i]);
}
int main(){
	freopen("park.in" ,"r",stdin );
	freopen("park.out","w",stdout);
	fread(ch,1,10000000,stdin);
	init();
	work();
	return 0;
}