记录编号	217903	评测结果	AAAAAAAATA
题目名称	[WC 2013] 糖果公园	最终得分	90
用户昵称	dashgua	是否通过	未通过
代码语言	C++	运行时间	31.095 s
提交时间	2016-01-06 17:39:31	内存使用	15.37 MiB

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

template<class Num>void read(Num &x)
{
	char c; int flag = 1;	
	
	while((c = getchar()) < '0' || c > '9')
		if(c == '-') flag *= -1;
	x = c - '0';
	while((c = getchar()) >= '0' && c <= '9')
		x *= 10, x += c - '0';
	x *= flag;
}
template<class Num>void write(Num x)
{
	if(x == 0) {putchar('0'); return;}
	static char s[20]; int sl = 0;
	if(x < 0) x = -x, putchar('-');
	while(x) s[sl++] = x % 10 + '0', x /= 10;
	while(sl) putchar(s[--sl]);
}

const int maxn = 1e5 + 20, logN = 17;
#define X first
#define Y second

int n, m, q;
long long v[maxn];
int w[maxn];
int cnt[maxn];

std::pair<int,int> edge[maxn << 1];
int head[maxn], Es;
int fa[maxn], F[maxn][logN], dep[maxn];

int B[maxn], Bs, Bn;
int st[maxn], top, size[maxn];

long long Ans[maxn], ans;
int col[maxn], sta[maxn];

struct Query
{
	int u, v, a, b, t, id;
}query[maxn];

struct Operation
{
	int x, y, z;
}op[maxn];

int qs, os;

bool cmp(const Query &x,const Query &y)
{
	return x.a == y.a ? (x.b == y.b ? x.t < y.t : x.b < y.b) : x.a < y.a;
}
inline void newedge(int u,int v)
{
	edge[++Es] = std::make_pair(v, head[u]), head[u] = Es;
}
void dfs(int a,int Fa)
{
	fa[a] = Fa, dep[a] = dep[Fa] + 1;
	st[++top] = a;
	
	F[a][0] = fa[a];
	for(int i = 1; i < logN; i++)
		F[a][i] = F[F[a][i - 1]][i - 1];
	
	for(int i = head[a]; i; i = edge[i].Y)
	{
		int v = edge[i].X;
	
		if(v == Fa) continue;
		dfs(v, a), size[a] += size[v];
	
		if(size[a] >= Bs)
		{
			size[a] = 0, ++Bn;
			while(st[top] != a)
				B[st[top--]] = Bn;
		}
	}
	size[a]++;
}

inline void del(int a)
{
	if(sta[a])
	{
		ans -= v[col[a]] * w[cnt[col[a]]];
		cnt[col[a]] --;
	}
}
inline void ins(int a)
{
	if(sta[a])
	{
		cnt[col[a]] ++;
		ans += v[col[a]] * w[cnt[col[a]]];
	}
}
inline void rev(int a)
{
	del(a), sta[a] ^= 1, ins(a);
}
inline void update(int a,int v)
{
	del(a), col[a] = v, ins(a);
}
inline int getlca(int u,int v)
{
	if(dep[u] < dep[v]) std::swap(u, v);
	
	for(int i = logN - 1; i >= 0; i--)
		if(dep[F[u][i]] >= dep[v]) u = F[u][i];
	
	if(u == v) return u;
	
	for(int i = logN - 1; i >= 0; i--)
		if(F[u][i] != F[v][i]) u = F[u][i], v = F[v][i];
	
	return F[u][0];
}
inline void rot(int x,int y,int s)
{
	rev(getlca(x, s));
	rev(getlca(y, s));
	
	while(x != y)
	{
		if(dep[x] < dep[y]) std::swap(x, y);
		rev(x), x = fa[x];
	}
}
void solve()
{
	std::sort(query + 1, query + qs + 1, cmp);
	
	int u = 1, v = 1, t = os;
	
	rev(1);
	
	for(int i = 1; i <= qs; i++)
	{
		while(t < query[i].t)
			++t, update(op[t].x, op[t].y); 
		while(t > query[i].t)
			update(op[t].x, op[t].z), t--;
		
		rot(u, query[i].u, v);
		u = query[i].u;
		rot(v, query[i].v, u);
		v = query[i].v;
		
		Ans[query[i].id] = ans;
	}
	
	for(int i = 1; i <= qs; i++)
		write(Ans[i]), puts("");
}
void init()
{
	read(n), read(m), read(q);
	
	for(int i = 1; i <= m; i++) read(v[i]);
	for(int i = 1; i <= n; i++) read(w[i]);
	
	for(int i = 1, u, v; i < n; i++)
	{
		read(u), read(v);
		newedge(u, v), newedge(v, u);
	}
	
	Bs = pow(n + 1, (double) 2 / 3), dfs(1, 0);
	while(top) B[st[top--]] = Bn;
	
	for(int i = 1; i <= n; i++) read(col[i]);
	
	for(int i = 1, t, x, y; i <= q; i++)
	{
		read(t), read(x), read(y), t ^= 1;
		
		if(t == 0)
		{
			if(B[x] > B[y]) std::swap(x, y);
			query[++qs] = (Query){x, y, B[x], B[y], os, qs};
		}
		else
		{
			op[++os] = (Operation){x, y, col[x]};
			col[x] = y;
		}
	}
}
int main()
{
	freopen("park.in","r",stdin);
	freopen("park.out","w",stdout);

	init();
	
	solve();

	fclose(stdin);
	fclose(stdout);
	return 0;
}