这种题显然要用树上莫队
何为树上莫队?就是在树上跑莫队算法就是先把树分块,然后把询问离线,按照左端点所在块为第一关键字,右端点所在块为第二关键字,时间戳(如果有修改操作)为第三关键字排序,然后依次处理.树上莫队要每个点记录是否访问,移动端点时需要把移动前和移动后的点之间的路径上的点(除了上述两点的lca)的访问状态取反,算答案时单独对询问两端点的lca算贡献
然后用莫队的那一套理论直接做就好了
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
using namespace std;
const int N=100000+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],tot=1;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot;
}
int n,m,q,szm,mm[N],nm,a[N],b[N],ti,mdf[N][3];
int fa[N],de[N],sz[N],son[N],top[N];
LL v[N],w[N],na,an[N];
int st[N],tp;
void dfs1(int x)
{
sz[x]=1;
int la=tp;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==fa[x]) continue;
fa[y]=x,de[y]=de[x]+1,dfs1(y),sz[x]+=sz[y];
if(sz[son[x]]<sz[y]) son[x]=y;
if(tp-la>=szm)
{
++nm;
while(tp!=la) mm[st[tp--]]=nm;
}
}
st[++tp]=x;
}
void dfs2(int x,int ntp)
{
top[x]=ntp;
if(son[x]) dfs2(son[x],ntp);
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
il int glca(int x,int y)
{
while(top[x]!=top[y])
{
if(de[top[x]]<de[top[y]]) swap(x,y);
x=fa[top[x]];
}
return de[x]<de[y]?x:y;
}
bool vis[N];
il void ad(int ww){++b[ww],na+=v[ww]*w[b[ww]];}
il void dl(int ww){na-=v[ww]*w[b[ww]],--b[ww];}
il void cg(int x)
{
if(vis[x]) dl(a[x]);
else ad(a[x]);
vis[x]^=1;
}
il void mv(int x,int y)
{
if(de[x]<de[y]) swap(x,y);
while(de[x]!=de[y]) cg(x),x=fa[x];
while(x!=y) cg(x),x=fa[x],cg(y),y=fa[y];
}
struct qu
{
int l,r,t,id;
bool operator < (const qu &bb) const {return mm[l]!=mm[bb.l]?mm[l]<mm[bb.l]:(mm[r]!=mm[bb.r]?mm[r]<mm[bb.r]:t<bb.t);}
}qq[N];
int main()
{
n=rd(),m=rd(),q=rd();
szm=(int)pow(n,0.61);
for(int i=1;i<=m;++i) v[i]=rd();
for(int i=1;i<=n;++i) w[i]=rd();
for(int i=1;i<n;++i) add(rd(),rd());
dfs1(1);
while(tp) mm[st[tp--]]=nm;
dfs2(1,1);
for(int i=1;i<=n;++i) a[i]=rd();
for(int i=1;i<=q;++i)
{
int op=rd(),x=rd(),y=rd();
if(op==1)
{
if(mm[x]>mm[y]) swap(x,y);
qq[i-ti].l=x,qq[i-ti].r=y,qq[i-ti].t=ti,qq[i-ti].id=i-ti;
}
else mdf[++ti][0]=x,mdf[ti][1]=y;
}
sort(qq+1,qq+q-ti+1);
for(int i=1,l=1,r=1,t=0;i<=q-ti;l=qq[i].l,r=qq[i].r,++i)
{
while(t<qq[i].t)
{
++t;
int xx=mdf[t][0],yy=mdf[t][1];mdf[t][2]=a[xx];
if(vis[xx]) dl(a[xx]),ad(yy);
a[xx]=yy;
}
while(t>qq[i].t)
{
int xx=mdf[t][0],yy=mdf[t][2];
if(vis[xx]) dl(a[xx]),ad(yy);
a[xx]=yy;
--t;
}
mv(l,qq[i].l),mv(r,qq[i].r);
int lca=glca(qq[i].l,qq[i].r);
cg(lca),an[qq[i].id]=na,cg(lca);
}
for(int i=1;i<=q-ti;++i) printf("%lld
",an[i]);
return 0;
}