Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,s;

#define MAXN 100010

int val[MAXN],wei[MAXN],type[MAXN],type_[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int dep[MAXN],top[MAXN],siz[MAXN],son[MAXN],fa[MAXN];

int ind[MAXN],oud[MAXN],pnt[MAXN << 1],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	ind[k] = ++tot;pnt[tot] = k;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	oud[k] = ++tot;pnt[tot] = k;

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

struct change

{

	int tim,pos,pre,val;

}c[MAXN];

int ctot = 0;

struct query

{

	int tim,l,r,k;

	long long ans;

}q[MAXN];

int qtot = 0;

int pos[MAXN << 1];

bool cmp(query a,query b)

{

	if(pos[a.l] != pos[b.l])return pos[a.l] < pos[b.l];

	if(pos[a.r] != pos[b.r])return pos[a.r] < pos[b.r];

	return a.tim < b.tim;

}

bool cmp_tim(query a,query b){return a.tim < b.tim;}

int cnt[MAXN];

long long ans = 0;

void add(int k)

{

	int w = type[k];

	++cnt[w];

	ans += 1ll * val[w] * wei[cnt[w]];

	return;

}

void rem(int k)

{

	int w = type[k];

	ans -= 1ll * val[w] * wei[cnt[w]];

	--cnt[w];

	return;

}

int vis[MAXN];

void set(int k)

{

	if(vis[k] == 1)rem(k);

	if(vis[k] == 0)add(k);

	vis[k] ^= 1;

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&s);

	for(R int i = 1;i <= m;++i)val[i] = rd();

	for(R int i = 1;i <= n;++i)wei[i] = rd();

	R int a,b;

	for(R int i = 1;i < n;++i)

	{

		a = rd();b = rd();

		add(a,b);

	}

	for(R int i = 1;i <= n;++i)type_[i] = type[i] = rd();

	dfs1(1,1);dfs2(1,1);

	R int opt,x,y;

	for(R int i = 1;i <= s;++i)

	{

		opt = rd();x = rd();y = rd();

		if(opt == 0)

		{

			c[++ctot] = (change){i,x,type_[x],y};

			type_[x] = y;

		}

		else

		{

			++qtot;

			q[qtot].tim = i;

			R int lca = LCA(x,y);

			if(lca == x || lca == y)

			{

				q[qtot].l = ind[x];

				q[qtot].r = ind[y];

				if(q[qtot].l > q[qtot].r)swap(q[qtot].l,q[qtot].r);

				q[qtot].k = -1;

			}

			else

			{

				if(ind[x] > ind[y])swap(x,y);

				q[qtot].l = oud[x];q[qtot].r = ind[y];

				q[qtot].k = lca;

			}

		}

	}

	int blo = pow(tot,0.66666666666);

	for(int i = 1;i <= tot;++i)pos[i] = (i - 1) / blo + 1;

	sort(q + 1,q + 1 + qtot,cmp);

	for(int i = 1,l = 1,r = 0,ptr = 0;i <= qtot;++i)

	{

		for(;ptr != ctot && c[ptr + 1].tim < q[i].tim;)

		{

			++ptr;

			if(l <= ind[c[ptr].pos] && ind[c[ptr].pos] <= r)set(c[ptr].pos);

			if(l <= oud[c[ptr].pos] && oud[c[ptr].pos] <= r)set(c[ptr].pos);

			type[c[ptr].pos] = c[ptr].val;

			if(l <= ind[c[ptr].pos] && ind[c[ptr].pos] <= r)set(c[ptr].pos);

			if(l <= oud[c[ptr].pos] && oud[c[ptr].pos] <= r)set(c[ptr].pos);

		}

		for(;c[ptr].tim > q[i].tim;)

		{

			if(l <= ind[c[ptr].pos] && ind[c[ptr].pos] <= r)set(c[ptr].pos);

			if(l <= oud[c[ptr].pos] && oud[c[ptr].pos] <= r)set(c[ptr].pos);

			type[c[ptr].pos] = c[ptr].pre;

			if(l <= ind[c[ptr].pos] && ind[c[ptr].pos] <= r)set(c[ptr].pos);

			if(l <= oud[c[ptr].pos] && oud[c[ptr].pos] <= r)set(c[ptr].pos);

			--ptr;

		}

		for(;l > q[i].l;--l)set(pnt[l - 1]);

		for(;r < q[i].r;++r)set(pnt[r + 1]);

		for(;l < q[i].l;++l)set(pnt[l]);

		for(;r > q[i].r;--r)set(pnt[r]);

		if(q[i].k != -1)set(q[i].k);

		q[i].ans = ans;

		if(q[i].k != -1)set(q[i].k);

	}

	sort(q + 1,q + 1 + qtot,cmp_tim);

	for(int i = 1;i <= qtot;++i)printf("%lld\n",q[i].ans);

	return 0;

}