记录编号	155025	评测结果	AAAAAAAAAA
题目名称	[WC 2013] 糖果公园	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	32.086 s
提交时间	2015-03-26 11:58:56	内存使用	31.86 MiB

/****************************************\
* Author : ztx
* Title  :
* ALG    : ����Ī��
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;

char chin[10000000],chout[5000000],*pi=chin,*po=chout;

template <typename TP>
void read(TP &ret){
	ret=0;
	while(*pi<48) pi++;
	while(*pi>47) ret=ret*10+*pi++-48;
}

template <typename TP>
void print(TP x){
	static int tim=0; 
	static char p[30];
	while(x) p[++tim]=x%10+'0',x/=10;
	while(tim) *po++=p[tim--];
	*po++='\n';
}
/*
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

template <typename TP>
inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}
*/
typedef long long ll ;

#include <algorithm>
#include <cmath>

#define  maxn  100010LL
#define  maxm  100010LL
#define  maxq  100010LL
#define  maxk  18LL

//struct FST { int to , next ; } e[maxm<<1] ;
int next[maxm<<1] , to[maxm<<1] ;
int star[maxn] = {0} , tote = 1 ;
void AddEdge(int u , int v) { ++tote ; to[tote] = v ; next[tote] = star[u] ; star[u] = tote ; }

int n , m , timnow ;
ll ansnow ;
int cntblc , szblc , idx , top ;

int col[maxn] , cnt[maxn] = {0} , last[maxn] ;
int dfn[maxn] , sta[maxn] , belong[maxn] , dep[maxn] , size[maxn] , par[maxn][maxk] ;
ll ans[maxq] ;
bool vis[maxn] = {0} ;

struct QUERY {
	int u , v , lca , id , tim ;
	bool operator < (const QUERY& b) const {
		if (belong[u]!=belong[b.u]) return belong[u]<belong[b.u] ;
		if (belong[v] != belong[b.v]) return belong[v]<belong[b.v] ;
		return id < b.id ;
	}
} q[maxq] ;

struct CHANGE {
	int pos , from , to ;
} c[maxq] ;

inline void dfs(int u , int fa) {
int v , p ;
	sta[++top] = u ;
	par[u][0] = fa ;
	dfn[u] = ++idx ;
	dep[u] = dep[fa]+1 ;
	size[u] = 0 ;
	for (p = star[u] ; p ; p = next[p])
		if (v=to[p] , v!=fa) {
			dfs(v , u) ;
			size[u] += size[v] ;
			if (size[u] >= szblc) {
				size[u] = 0 ;
				cntblc ++ ;
				while (sta[top] != u) belong[sta[top--]] = cntblc ;
			}
		}
	size[u] ++ ;
}

inline void ST() {
int i , k ;
	Rep (k,1,maxk-1)
		Rep (i,1,n)
			par[i][k] = par[par[i][k-1]][k-1] ;
}

inline int LCA(int u , int v) {
	int k ;
	if (dep[u] < dep[v]) std::swap(u,v) ;
	Rev (k,maxk-1,0)
		if (dep[par[u][k]] >= dep[v]) u = par[u][k] ;
	if (u == v) return u ;
	Rev (k,maxk-1,0)
		if (par[u][k] != par[v][k])
			u = par[u][k] , v = par[v][k] ;
	return par[u][0] ;
}

ll v[maxn] , w[maxm] ;

inline void Reverse(int u) {
	if (vis[u]) { vis[u]=false;ansnow-=v[col[u]]*w[cnt[col[u]]--]; }
	else { vis[u]=true;ansnow+=v[col[u]]*w[++cnt[col[u]]]; }
}

inline void Modify(int u , int c) {
	if (vis[u]) {
		Reverse(u) ;
		col[u] = c ;
		Reverse(u) ;
	} else col[u] = c ;
}

inline void MoveTo(int u,int v) {
	while (u != v)
		if (dep[u] > dep[v]) Reverse(u) , u = par[u][0] ;
		else Reverse(v) , v = par[v][0] ;
}

inline void GetAns(int i) {
	Reverse(q[i].lca) ;
	ans[q[i].id] = ansnow ;
	Reverse(q[i].lca) ;
}


#include <ctime>

int main() {
int i , a , b , Q , cmd ;
	#define READ
	#ifdef  READ
		freopen("park.in" ,"r",stdin ) ;
		freopen("park.out","w",stdout) ;
	#endif
	fread(pi,1,10000000,stdin);
	read(n) , read(m) , read(Q) ;
	/* n ����� , m ��ɫ , Q ѯ�� */
	szblc = (int)pow(n,2.0/3.0)*.5 ;
	Rep (i,1,m) read(v[i]) ;
	Rep (i,1,n) read(w[i]) ;
	Rep (i,2,n) {
		read(a) , read(b) ;
		AddEdge(a,b) , AddEdge(b,a) ;
	}
	Rep (i,1,n) read(col[i]) , last[i] = col[i] ;
	cntblc = idx = dep[0] = ansnow = top = 0 ;
	dfs(1,0) ;
	cntblc ++ ;
	while (top) belong[sta[top--]] = cntblc ;
	ST() ;
	int totq = 0 , totc = 0 ;
	Rep (i,1,Q) {
		read(cmd) , read(a) , read(b) ;
		if (cmd) {
			totq ++ ;
			if (belong[a] > belong[b]) std::swap(a,b) ;
			q[totq].lca = LCA(a,b) ;
			q[totq].id = totq , q[totq].u = a , q[totq].v = b ;
			q[totq].tim = totc ;
		} else {
			totc ++ ;
			c[totc].pos = a ;
			c[totc].from = last[a] ;/*u����һ����ɫ*/
			c[totc].to = last[a] = b ;
		}
	}
	timnow = 1 ;
	std::sort(q+1,q+totq+1) ;
	while (timnow <= q[1].tim) Modify(c[timnow].pos,c[timnow].to) , ++timnow ;
	MoveTo(q[1].u,q[1].v) ;
	GetAns(1) ;
	Rep (i,2,totq) {
		while (timnow <= q[i].tim) Modify(c[timnow].pos,c[timnow].to) , ++timnow ;
		while (timnow-1 > q[i].tim) Modify(c[timnow-1].pos,c[timnow-1].from) , --timnow ;
		MoveTo(q[i-1].u,q[i].u) ;
		MoveTo(q[i-1].v,q[i].v) ;
		GetAns(i) ;
	}
	Rep (i,1,totq) print(ans[i]);//printf("%lld\n", ans[i]) ;
	fwrite(chout,1,po-chout,stdout);

	//printf("%.2lf\n",clock()/1000.0) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}
/*
4 3 3
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 4 2
0 2 1
1 1 2
*/