救救孩子！！！

用莫队做的，最后一个点没过

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define re register
#define ll long long
#define isnum(x) (x<58&&x>47)
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fd(i,a,b) for(re int i=a;i>=b;--i)
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isnum(ch))ch=getchar();
    while(isnum(ch))ans=(ans<<1)+(ans<<3)+(ch^48),ch=getchar();
    return ans;
}
const int maxn=200020;
struct edge{
    int to,nxt;
}e[maxn<<1];
struct query{
    int l,r,lca,time,id;
}q[maxn];
struct change{
    int pos,val;
}c[maxn];
int siz,blck,cnte,cntc,cntq,cntn,n,m,Q;
int vis[maxn],cnt[maxn],val[maxn],wol[maxn],head[maxn],color[maxn],belong[maxn];
int dep[maxn],a[maxn],frst[maxn],lst[maxn],fa[maxn][30];
inline void add_edge(int u,int v){
    e[++cnte]=(edge){v,head[u]};head[u]=cnte;
    e[++cnte]=(edge){u,head[v]};head[v]=cnte;
}
inline bool cmp(query a,query b){
    return (belong[a.l]^belong[b.l])?(belong[a.l]<belong[b.l]):((belong[a.r]^belong[b.r])?(belong[a.r]<belong[b.r]):(a.time<b.time));
}
inline void dfs(int u){
    a[++cntn]=u;
    frst[u]=cntn;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(dep[v])continue;
        dep[v]=dep[u]+1;
        fa[v][0]=u;
        for(re int j=1;(1<<j)<=dep[v];++j)
            fa[v][j]=fa[fa[v][j-1]][j-1];
        dfs(v);
    }
    a[++cntn]=u;
    lst[u]=cntn;
}
inline int getlca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(re int i=20;i+1;--i)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
    if(!(u^v))return u;
    for(re int i=20;i+1;--i)if(fa[u][i]^fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
ll now,ans[maxn];
inline void add(int pos){
    now+=1ll*val[color[pos]]*wol[++cnt[color[pos]]];
}
inline void del(int pos){
    now-=1ll*val[color[pos]]*wol[cnt[color[pos]]--];
}
inline void _work(int pos){
    vis[pos]?del(pos):add(pos);
    vis[pos]^=1;
}
inline void _change(int pos){
    if(vis[c[pos].pos]){
        _work(c[pos].pos);
        swap(color[c[pos].pos],c[pos].val);
        _work(c[pos].pos);
    }
    else swap(color[c[pos].pos],c[pos].val);
}
int main(){
    n=read();m=read();Q=read();
    fp(i,1,m)val[i]=read();
    fp(i,1,n)wol[i]=read();
    fp(i,2,n)add_edge(read(),read());
    fp(i,1,n)color[i]=read();
    dep[1]=1;
    dfs(1);
    siz=pow(cntn,2.0/3.0);
    blck=ceil((double)cntn/siz);
    fp(i,1,blck)
        fp(j,siz*(i-1)+1,i*siz)
            belong[j]=i;
    fp(i,1,Q){
        int opt=read(),x=read(),y=read();
        if(opt){
            int lca=getlca(x,y);
            q[++cntq].time=cntc;
            q[cntq].id=cntq;
            if(frst[x]>frst[y])swap(x,y);
            if(x^lca)q[cntq].l=lst[x],q[cntq].lca=lca;
            else q[cntq].l=frst[x];
            q[cntq].r=frst[y];
        }
        else {
            c[++cntc].pos=x;
            c[cntc].val=y;
        }
    }
    sort(q+1,q+cntq+1,cmp);
    int l=1,r=0,time=0;
    fp(i,1,cntq){
        int lca=q[i].lca;
        while(l<q[i].l)_work(a[l++]);
        while(l>q[i].l)_work(a[--l]);
        while(r<q[i].r)_work(a[++r]);
        while(r>q[i].r)_work(a[r--]);
        while(time<q[i].time)_change(++time);
        while(time>q[i].time)_change(time--);
        if(lca)_work(lca);
        ans[q[i].id]=now;
        if(lca)_work(lca);
    }
    for(re int i=1;i<=cntq;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}