AC on [1,4],TLE on [6,10]

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
#define endl '\n'
int n,m,q,v[100005],w[100005],c[100005],cntq,cntr,block,fa[100005],sz[100005],dep[100005],son[100005],top[100005],dfn[300005],tot,first[100005],second[100005],pos[300005],cnt[100005],l = 1,r,t,ans,sum[100005],vis[300005];
vector<int> map[100005];
struct ask{
	int l,r,lca,id,t;
}qq[100005];
bool cmp(ask x,ask y)
{
	if(pos[x.l] != pos[x.r]) return pos[x.l] < pos[y.l];
	if(pos[x.r] != pos[y.r]) return pos[x.r] < pos[y.r];
	return x.t < y.t;
}
struct upd{
	int d,x;
}qr[100005];
void dfs1(int u,int father)
{
	dep[u] = dep[father] + 1;
	fa[u] = father;
	sz[u] = 1;
	son[u] = -1;
	for(int i = 0; i < map[u].size(); i++)
	{
		int v = map[u][i];
		if(v == fa[u]) continue;
		dfs1(v,u);
		sz[u] += sz[v];
		if(son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v;
	}
}
void dfs2(int u,int tp)
{
	top[u] = tp;
	if(son[u] == -1) return;
	dfs2(son[u],tp);
	for(int i = 0; i < map[u].size(); i++)
	{
		int v = map[u][i];
		if(v == fa[u] || v == son[u]) continue;
		dfs2(v,v);
	}
}
int lca(int u,int v)
{
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]]) swap(u,v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}
void dfs3(int u)
{
	dfn[++tot] = u;
	first[u] = tot;
	for(int i = 0; i < map[u].size(); i++)
	{
		int v = map[u][i];
		if(v == fa[u]) continue;
		dfs3(v);
	}
	dfn[++tot] = u;
	second[u] = tot;
}
void add(int x)
{
	ans += v[c[x]] * w[++cnt[c[x]]];
}
void pop(int x)
{
	ans -= v[c[x]] * w[cnt[c[x]]--];
}
void move(int x)
{
	vis[x] ? pop(x) : add(x);
	vis[x] ^= 1;
}
void updata(int t)
{
	if(vis[qr[t].d])
	{
		move(qr[t].d);
		swap(c[qr[t].d],qr[t].x);
		move(qr[t].d);
	}
	else swap(c[qr[t].d],qr[t].x);
}
inline int read(){
	char _c = getchar();
	int _x = 0, _s = 1;
	while(_c<'0' || _c>'9'){
		if(_c == '-') _s = -1;
		_c = getchar();
	}
	while(_c >= '0' && _c<='9'){
		_x = _x*10+_c-'0';
		_c = getchar();
	}
	return _x * _s;
}
signed main()
{
	//cin >> n >> m >> q;
	n = read();
	m = read();
	q = read();
	for(int i = 1; i <= m; i++)
	{
		//cin >> v[i];
		v[i] = read();
	}
	for(int i = 1; i <= n; i++)
	{
		//cin >> w[i];
		w[i] = read();
	}
	for(int i = 1; i < n; i++)
	{
		int u,v;
		//cin >> u >> v;
		u = read();
		v = read();
		map[u].push_back(v);
		map[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	dfs3(1);
	block = pow(tot,2.0/3.0);
	for(int i = 1; i <= tot; i++)
	{
		pos[i] = (i-1)/block+1;
	}
	for(int i = 1; i <= n; i++)
	{
		c[i] = read();
		//cin >> c[i];
	}
	for(int i = 1; i <= q; i++)
	{
		int opt,x,y;
		cin >> opt >> x >> y;
		if(opt == 0) qr[++cntr] = {x,y};
		else if(opt == 1)
		{
			int l = lca(x,y);
			if(first[x] > first[y]) swap(x,y);
			if(l == x) qq[++cntq] = {first[x],first[y],0,cntq,cntr};
			else qq[++cntq] = {second[x],first[y],l,cntq,cntr};
		}
	}
	sort(qq + 1,qq + cntq + 1,cmp);
	for(int i = 1; i <= cntq; i++)
	{
		while(l > qq[i].l) move(dfn[--l]);
		while(r < qq[i].r) move(dfn[++r]);
		while(l < qq[i].l) move(dfn[l++]);
		while(r > qq[i].r) move(dfn[r--]);
		while(t < qq[i].t) updata(++t);
		while(t > qq[i].t) updata(t--);
		if(qq[i].lca) move(qq[i].lca);
		sum[qq[i].id] = ans;
		if(qq[i].lca) move(qq[i].lca);
	}
	for(int i = 1; i <= cntq; i++)
	{
		cout << sum[i] << endl;
	}
	return 0;
}