思路：
带修改树上莫队（模板）；
来，上代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 100005
#define ll long long struct QueryType {
ll u,v,t,id;
};
struct QueryType qu[maxn]; struct ChangeType {
ll to,x,h;
};
struct ChangeType cha[maxn]; ll n,m,q,ti[maxn],totq,totc,vi[maxn],wi[maxn];
ll siz,deep[maxn],f[maxn],top[maxn],bel[maxn],size[maxn];
ll E[maxn<<],V[maxn<<],head[maxn],cnt,dis[maxn],ans[maxn]; bool if_[maxn]; inline void in(ll &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} void pre(ll now,ll fa)
{
deep[now]=deep[fa]+,size[now]=;
bel[now]=((++cnt)+)/siz,f[now]=fa;
for(ll i=head[now];i;i=E[i])
{
if(V[i]==fa) continue;
pre(V[i],now),size[now]+=size[V[i]];
}
} void dfs(ll now,ll chain)
{
ll pos=;top[now]=chain;
for(ll i=head[now];i;i=E[i])
{
if(V[i]==f[now]) continue;
if(size[V[i]]>size[pos]) pos=V[i];
}
if(pos==) return ;
dfs(pos,chain);
for(ll i=head[now];i;i=E[i])
{
if(V[i]==pos||V[i]==f[now]) continue;
dfs(V[i],V[i]);
}
} ll solve_lca(ll x,ll y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
x=f[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
return x;
} bool cmp(QueryType aa,QueryType bb)
{
if(bel[aa.u]==bel[bb.u])
{
if(bel[aa.v]==bel[bb.v]) return aa.t<bb.t;
else return bel[aa.v]<bel[bb.v];
}
else return bel[aa.u]<bel[bb.u];
} inline void change(ll x)
{
if(if_[cha[x].to])
{
cnt-=wi[ti[dis[cha[x].to]]]*vi[dis[cha[x].to]];
ti[dis[cha[x].to]]--;
}
cha[x].h=dis[cha[x].to];
dis[cha[x].to]=cha[x].x;
if(if_[cha[x].to])
{
ti[cha[x].x]++;
cnt+=wi[ti[cha[x].x]]*vi[cha[x].x];
}
} inline void unchange(ll x)
{
if(if_[cha[x].to])
{
cnt-=wi[ti[cha[x].x]]*vi[cha[x].x];
ti[cha[x].x]--;
}
dis[cha[x].to]=cha[x].h;
if(if_[cha[x].to])
{
ti[cha[x].h]++;
cnt+=wi[ti[cha[x].h]]*vi[cha[x].h];
}
} inline void updata(ll x)
{
if(if_[x])
{
cnt-=wi[ti[dis[x]]]*vi[dis[x]];
ti[dis[x]]--;
}
else
{
ti[dis[x]]++;
cnt+=wi[ti[dis[x]]]*vi[dis[x]];
}
if_[x]=!if_[x];
} inline void out(ll x)
{
if(x>) out(x/);
putchar(x%+);
} int main()
{
freopen("park.in","r",stdin);
freopen("park.out","w",stdout);
in(n),in(m),in(q);ll u,v;siz=sqrt(n);
for(ll i=;i<=m;i++) in(vi[i]);
for(ll i=;i<=n;i++) in(wi[i]);
for(ll i=;i<n;i++)
{
in(u),in(v);
E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
}
for(ll i=;i<=n;i++) in(dis[i]);
cnt=,pre(,),dfs(,);ll ty;
for(ll i=;i<=q;i++)
{
in(ty);
if(ty)
{
in(qu[++totq].u),in(qu[totq].v),qu[totq].t=totc,qu[totq].id=totq;
if(bel[qu[totq].u]>bel[qu[totq].v]) swap(qu[totq].u,qu[totq].v);
}
else in(cha[++totc].to),in(cha[totc].x);
}
sort(qu+,qu+totq+,cmp),u=,v=,cnt=;ll t=;
for(ll no=;no<=totq;no++)
{
while(t<qu[no].t) change(++t);
while(t>qu[no].t) unchange(t--);
ll lca=solve_lca(u,qu[no].u);
while(u!=lca) updata(u),u=f[u];u=qu[no].u;
while(u!=lca) updata(u),u=f[u];u=qu[no].u;
lca=solve_lca(v,qu[no].v);
while(v!=lca) updata(v),v=f[v];v=qu[no].v;
while(v!=lca) updata(v),v=f[v];v=qu[no].v;
lca=solve_lca(u,v);
updata(lca),ans[qu[no].id]=cnt,updata(lca);
}
for(ll i=;i<=totq;i++) out(ans[i]),putchar('\n');
fclose(stdin),fclose(stdout);
return ;
}