鄙人不才，敲了一个常数巨大的括号序莫队，开O2卡着5.9s过，不知道哪里有问题。

#include<bits/stdc++.h>
#define N 100010
#define LL long long
#define ULL unsigned long long
#define DB double
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define tep(i,u) for(int i=head[u];~i;i=e[i].nxt)
#define INF 0x3f3f3f3f
using namespace std;
template <typename T> inline void read(T &a)
{
	a=0;T w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+(ch^48);ch=getchar();}
	a*=w;
}
template <typename T,typename ...Args> inline
void read(T &x,Args &...args){read(x);read(args...);}
inline void swap(int &a,int &b){a^=b;b^=a;a^=b;}
int n,m,Q,head[N],cc;
LL val[N],wei[N],a[N],ans[N];
struct EDGE{int v,nxt;}e[N<<1];
inline void add_edge(int u,int v)
{
	e[++cc].v=v;e[cc].nxt=head[u];head[u]=cc;
	e[++cc].v=u;e[cc].nxt=head[v];head[v]=cc;
}
int dfn[N<<1],tim,st[N],ed[N],belong[N<<1],blen,qcc,ccc;//括号序和分块 
struct QUERY//这是询问 
{
	int l,r,dfn,lca,id;
	QUERY(int li,int ri,int d,int lc,int i): l(li),r(ri),dfn(d),lca(lc),id(i){}
	QUERY(){}
	bool operator < (const QUERY &y) const
	{
		return (belong[l]^belong[y.l]) ? belong[l]<belong[y.l] : ((belong[r]^belong[y.r]) ? belong[r]<belong[y.r] : dfn<y.dfn);
	}
}q[N];
struct CHANGE//这是修改 
{
	int pos,dfn;
	LL val;
	CHANGE(int p,LL v,int d): pos(p),val(v),dfn(d){}
	CHANGE(){}
}c[N];
namespace TA//这是树剖 
{
	int dep[N],siz[N],son[N],fa[N],top[N];
	inline void dfs1(int u)
	{
		st[dfn[++tim]=u]=tim;
		siz[u]=1,dep[u]=dep[fa[u]]+1;
		tep(i,u)
		{
			int v=e[i].v;if(v==fa[u]) continue;
			fa[v]=u;dfs1(v);
			if(!son[u]||siz[son[u]]<siz[v]) son[u]=v;
		}
		ed[dfn[++tim]=u]=tim;
	}
	inline void dfs2(int u,int tp)
	{
		top[u]=tp;if(son[u]) dfs2(son[u],tp);
		tep(i,u)
		{
			int v=e[i].v;if(v==fa[u]||v==son[u]) continue;
			dfs2(v,v);
		}
	}
	inline void work(){fa[1]=0;dfs1(1);dfs2(1,1);}
}
inline int get_lca(int a,int b)//朴实无华的树剖LCA 
{
	while(TA::top[a]!=TA::top[b])
	{
		if(TA::dep[TA::top[a]]>TA::dep[TA::top[b]]) a=TA::fa[TA::top[a]];
		else b=TA::fa[TA::top[b]];
	}
	return TA::dep[a]<TA::dep[b] ? a:b;
}
int cnt[N];bool vis[N];
LL now;
inline void add(LL x){cnt[x]++;now+=val[x]*wei[cnt[x]];}//增加一个x糖果 
inline void del(LL x){now-=val[x]*wei[cnt[x]];cnt[x]--;}//减少一个x糖果 
inline void add_dfn(int x)//增加节点x上的糖果 
{
	if(vis[x]) del(a[x]);
	else add(a[x]);
	vis[x]^=1;
}
inline void chan(int x)//朴实无华的修改 
{
	if(vis[c[x].pos])
	{
		del(a[c[x].pos]);
		add(c[x].val);
	}
	swap(c[x].val,a[c[x].pos]);
}
signed main()
{
//	freopen("P4074_6.in","r",stdin);
	memset(head,-1,sizeof(head));
	read(n,m,Q);
	rep(i,1,m) read(val[i]);
	rep(i,1,n) read(wei[i]);
	rep(i,2,n)
	{
		int u,v;read(u,v);
		add_edge(u,v);
	}
	rep(i,1,n) read(a[i]);
	TA::work();
	
	blen=pow(tim,2.0/3.0);
	rep(i,1,tim) belong[i]=(i-1)/blen+1;
	
	rep(i,1,Q)
	{
		int opt,x,y;read(opt,x,y);
		if(opt^1) c[++ccc]={x,y,i};
		else
		{
			if(st[x]>st[y]) swap(x,y);
			int lca=get_lca(x,y);
			++qcc;q[qcc]={lca==x ? st[x]:ed[x],st[y],ccc,lca,qcc};
		}
	}
	
	sort(q+1,q+1+qcc);
	
	int l=1,r=0,nd=0;
	rep(i,1,qcc)
	{	
		while(l<q[i].l) add_dfn(dfn[l++]);
		while(l>q[i].l) add_dfn(dfn[--l]);
		while(r<q[i].r) add_dfn(dfn[++r]);
		while(r>q[i].r) add_dfn(dfn[r--]);
		while(nd<q[i].dfn) chan(++nd);
		while(nd>q[i].dfn) chan(nd--);
		if(!vis[q[i].lca])
		{
			add(a[q[i].lca]);
			ans[q[i].id]=now;
			del(a[q[i].lca]);
		}
		else ans[q[i].id]=now;
	}
	rep(i,1,qcc) printf("%lld\n",ans[i]);
	return 0;
}