传送门：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3052
思路：带修改的树上莫队。
比不带修改的多加上一个时间维。
对于时间的移动，那么就模拟一下这段时间的修改，更新答案。
然后块的大小要设为n^(2/3)。
至于时间复杂度的证明...
取B = n ^ (2 / 3)，设 nBlo为块的个数，用bloNum[v]来代表v所在块的编号。（block number）
则同一个块内任意两结点的距离为O(n ^ (2 / 3))的。
按照之前我说的方式对询问进行排序，按顺序作答。
注意到(bloNum[curV], bloNum[curU])一共有nBlo ^ 2个取值。
那么如果移动一次，curV还在原来的块，curU还在原来的块，这种移动的总时间复杂度是O(nBlo ^ 2 * q)的。（因为curTi还要移动）
如果移动一次，curV不在原来的块，curU不在原来的块，这种移动发生的次数最多为 nBlo ^ 2。因为我是排好序的了嘛，相同块的是放在一起的。而这种移动发生一次最坏是O(n + n + q) = O(n)。(n、q是同阶的)
所以这样回答所有询问，时间复杂度就是O(nBlo ^ 2 * n)的。
由于B = n ^ (2 / 3)，块的大小介于[B, 3 * B]之间。
则nBlo = O(n ^ (1 / 3))
则时间复杂度为O(n ^ (5 / 3))。
——来自vfk的博客http://vfleaking.blog.163.com/blog/static/174807634201311011201627/
然后就没有然后了。
（一不小心TLE了3次.....捂脸，好像块的大小设为小于n^(2/3)要快一些...）
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=100010,maxm=200010,maxk=20;
using namespace std;
typedef long long ll;
struct oper{int x,v;}op[maxn];
struct que{int id,u,v,t;}q[maxn];
int n,m,Q,w[maxn],v[maxn],fa[maxn][maxk],dep[maxn],s[maxn],c[maxn],tim,ask,sz,cnt,bel[maxn];
int pre[maxm],now[maxn],son[maxm],tot,timm,dfn[maxn],sta[maxn],top;
ll ans[maxn],res;bool bo[maxn];char ch;
void read(int &x){
for (ch=getchar();!isdigit(ch);ch=getchar());
for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
bool cmp(que a,que b){
if (bel[a.u]!=bel[b.u]) return bel[a.u]<bel[b.u];
else if (bel[a.v]!=bel[b.v]) return bel[a.v]<bel[b.v];
else return a.t<b.t;
}
void getfa(int x,int f){
dfn[x]=++timm,dep[x]=dep[f]+1,fa[x][0]=f;
for (int i=1;i<maxk;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (int y=now[x];y;y=pre[y]) if (son[y]!=f) getfa(son[y],x);
}
int lca(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
for (int i=0,h=dep[u]-dep[v];h;i++,h>>=1) if (h&1) u=fa[u][i];
if (u==v) return u;
for (int i=maxk-1;i>=0;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
void getbck(int x,int f){
int bot=top;
for (int y=now[x];y;y=pre[y])
if (son[y]!=f){
getbck(son[y],x);
if (top-bot>=sz) for (++cnt;top!=bot;) bel[sta[top--]]=cnt;
}
sta[++top]=x;
}
void update(int x){
if (bo[x]) res-=1ll*v[c[x]]*w[s[c[x]]--];
else res+=1ll*v[c[x]]*w[++s[c[x]]];
bo[x]^=1;
}
void update(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
while (dep[u]!=dep[v]) update(u),u=fa[u][0];
while (u!=v) update(u),update(v),u=fa[u][0],v=fa[v][0];
}
void change(int t){
int x=op[t].x;
if (bo[x]){
res-=1ll*v[c[x]]*w[s[c[x]]--];
res+=1ll*v[op[t].v]*w[++s[op[t].v]];
}
swap(op[t].v,c[x]);
}
void updatet(int t1,int t2){
for (int i=t1+1;i<=t2;i++) change(i);
for (int i=t1;i>=t2+1;i--) change(i);
}
void work(int k){
update(q[k-1].u,q[k].u),update(q[k-1].v,q[k].v),updatet(q[k-1].t,q[k].t);
int x=lca(q[k].u,q[k].v);update(x),ans[q[k].id]=res,update(x);
}
int main(){
//freopen("aa.in","r",stdin),freopen("aa.out","w",stdout);
scanf("%d%d%d",&n,&m,&Q);sz=(int)pow(n,2.0/3.0)*0.7;
for (int i=1;i<=m;i++) scanf("%d",&v[i]);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
for (int i=1;i<=n;i++) scanf("%d",&c[i]);
for (int i=1,x,y,z;i<=Q;i++){
scanf("%d%d%d",&x,&y,&z);
if (!x) op[++tim]=(oper){y,z};
else q[++ask]=(que){ask,y,z,tim};
}
getfa(1,0),getbck(1,0);
while (top) bel[sta[top--]]=cnt;
for (int i=1;i<=ask;i++) if (bel[q[i].u]>bel[q[i].v]) swap(q[i].u,q[i].v);
sort(q+1,q+1+ask,cmp);
//for (int i=1;i<=ask;i++) printf("%d
",bel[q[i].u]);
q[0]=(que){0,1,1,0};
for (int i=1;i<=ask;i++) work(i);
for (int i=1;i<=ask;i++) printf("%lld
",ans[i]);
return 0;
}
/*
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2
*/
/*
5 5 5
6 3 7 4 10
1 4 2 3 4
1 2
2 3
1 4
2 5
3 3 3 4 5
1 4 2
1 5 3
0 3 1
0 2 3
1 3 2
*/