1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cmath>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=1e5+10;
typedef long long ll;
int n,m,Q,_n,fa[maxn][23],_nsiz,dfn[maxn],dep[maxn],c[maxn],color[maxn];
ll v[maxn],w[maxn];
int ecnt,tim,st[maxn<<1],belong[maxn],top,head[maxn],to[maxn<<1],nxt[maxn<<1];
struct query{
int u,v,id;
ll ans;
inline bool operator < (const query&zp)const {return belong[u]<belong[zp.u] or (belong[u]==belong[zp.u] and (belong[v]<belong[zp.v] or (belong[v]==belong[zp.v] and id<zp.id)));}
}q[maxn];
inline bool cmp(query a,query b){return a.id<b.id;}
struct modify{
int pos,bef,aft,id;
}mo[maxn<<1];
inline void addedge(int a,int b){
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;
to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;
}
int dfs(int x,int f){
int siz=0;
fa[x][0]=f;dep[x]=dep[f]+1;
dfn[x]=++tim;
for(int i=0;i<=20;i++)fa[x][i+1]=fa[fa[x][i]][i];
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(u==f)continue;
siz+=dfs(u,x);
if(siz>=_nsiz){
_n++;
while(siz)belong[st[top--]]=_n,siz--;
}
}
st[++top]=x;
return siz+1;
}
inline int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i+1;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=20;i+1;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
bool vis[maxn];
int num[maxn];
inline void reverse(const int& x,ll &ans){
if(vis[x])ans-=1ll*w[num[color[x]]]*v[color[x]],num[color[x]]--;
else num[color[x]]++,ans+=1ll*w[num[color[x]]]*v[color[x]];
vis[x]^=1;
}
inline void solve(int x,int y,ll &ans){
while(x!=y){
if(dep[x]>dep[y])reverse(x,ans),x=fa[x][0];
else reverse(y,ans),y=fa[y][0];
}
}
inline void work(){
n=read(),m=read(),Q=read();
_nsiz=pow(n,0.666666666);
for(int i=1;i<=m;i++)v[i]=read();
for(int i=1;i<=n;i++)w[i]=read();
for(int i=1;i<n;i++)addedge(read(),read());
for(int i=1;i<=n;i++)c[i]=color[i]=read();
int cntq=0,cntm=0,x;
for(int i=1;i<=Q;i++){
if(read())q[++cntq].id=i,q[cntq].u=read(),q[cntq].v=read();
else mo[++cntm].id=i,mo[cntm].bef=c[(x=read())],mo[cntm].pos=x,mo[cntm].aft=c[x]=read();
}
dfs(1,0);
for(int i=1;i<=cntq;i++)if(dfn[q[i].v]<dfn[q[i].u])swap(q[i].u,q[i].v);
++_n;
while(top)belong[st[top--]]=_n;
sort(q+1,q+1+cntq);
int now=0;
long long ans=0;
for(int i=1;i<=cntq;i++){
while(now<cntm and mo[now+1].id<=q[i].id){
now++;
if(vis[mo[now].pos])ans-=w[num[color[mo[now].pos]]]*v[color[mo[now].pos]],num[color[mo[now].pos]]--;
color[mo[now].pos]=mo[now].aft;
if(vis[mo[now].pos])num[color[mo[now].pos]]++,ans+=1LL*w[num[color[mo[now].pos]]]*v[color[mo[now].pos]];
}
while(now>=1 and mo[now].id>=q[i].id){
if(vis[mo[now].pos])ans-=w[num[color[mo[now].pos]]]*v[color[mo[now].pos]],num[color[mo[now].pos]]--;
color[mo[now].pos]=mo[now].bef;
if(vis[mo[now].pos])num[color[mo[now].pos]]++,ans+=1LL*w[num[color[mo[now].pos]]]*v[color[mo[now].pos]];
now--;
}
if(i==1)solve(q[i].u,q[i].v,ans);
else solve(q[i].u,q[i-1].u,ans),solve(q[i].v,q[i-1].v,ans);
int lca=LCA(q[i].u,q[i].v);
reverse(lca,ans);
q[i].ans=ans;
reverse(lca,ans);
}
sort(q+1,q+1+cntq,cmp);
for(int i=1;i<=cntq;i++)printf("%lld\n",q[i].ans);
}
}
signed main(){
star::work();
return 0;
}
|
