题面
分析
树上带修莫队板子题。。。
开始没给分块大小赋初值T了好一会。。。
CODE
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename T>inline void read(T &num) {
char ch; while((ch=getchar())<'0'||ch>'9');
for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
}
const int MAXN = 100005;
int Block, n, m, q, V[MAXN], W[MAXN], a[MAXN], bel[MAXN], la[MAXN], val[MAXN];
LL ans[MAXN], Ans; bool vis[MAXN];
struct Change {
int i, u, v;
}C[MAXN];
struct Query {
int u, v, t, id;
inline bool operator <(const Query &o)const {
return bel[u] == bel[o.u] ? (bel[v] == bel[o.v] ? t < o.t : bel[v] < bel[o.v]) : bel[u] < bel[o.u];
}
}Q[MAXN];
int fir[MAXN], to[MAXN<<1], nxt[MAXN<<1], cnt;
inline void add(int x, int y) { to[++cnt] = y; nxt[cnt] = fir[x]; fir[x] = cnt; }
int f[MAXN][17], dep[MAXN], dfn[MAXN], tmr, stk[MAXN], tot, top;
void dfs(int u, int ff) {
int bot = top; dfn[u] = ++tmr;
dep[u] = dep[f[u][0]=ff] + 1;
for(int i = fir[u]; i; i = nxt[i])
if(to[i] != ff) {
dfs(to[i], u);
if(top-bot > Block) {
++tot; while(top > bot) bel[stk[top--]] = tot;
}
}
stk[++top] = u;
}
inline void Pre() {
for(int j = 1; j < 17; ++j)
for(int i = 1; i <= n; ++i)
f[i][j] = f[f[i][j-1]][j-1];
}
inline int lca(int u, int v) {
if(dep[v] > dep[u]) swap(u, v);
for(int i = 0; i < 17; ++i)
if((dep[u]-dep[v])&(1<<i)) u = f[u][i];
if(u == v) return u;
for(int i = 16; ~i; --i)
if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
}
inline void upd(int i) {
if(!vis[i]) {
vis[i] = 1;
Ans += 1ll * V[a[i]] * W[++val[a[i]]];
}
else {
vis[i] = 0;
Ans -= 1ll * V[a[i]] * W[val[a[i]]--];
}
}
inline void mdf(int i, int col) {
if(!vis[i]) { a[i] = col; return; }
upd(i), a[i] = col, upd(i);
}
inline void rev(int u, int v) {
while(u != v) {
if(dep[v] > dep[u]) swap(u, v);
upd(u), u = f[u][0];
}
}
int main () {
read(n), read(m), read(q); Block = pow(n, 0.67);
for(int i = 1; i <= m; ++i) read(V[i]);
for(int i = 1; i <= n; ++i) read(W[i]);
for(int i = 1, x, y; i < n; ++i) read(x), read(y), add(x, y), add(y, x);
for(int i = 1; i <= n; ++i) read(a[i]), la[i] = a[i];
dfs(1, 0); Pre();
if(top) ++tot; while(top) bel[stk[top--]] = tot;
int cntc = 0, cntq = 0, opt, x, y;
while(q--) {
read(opt), read(x), read(y);
if(!opt) C[++cntc] = (Change){ x, la[x], y }, la[x] = y;
else {
if(dfn[x] > dfn[y]) swap(x, y);
Q[++cntq] = (Query){ x, y, cntc, cntq };
}
}
sort(Q + 1, Q + cntq + 1);
int TIMES = 0, LCA = lca(Q[1].u, Q[1].v);
while(TIMES < Q[1].t) ++TIMES, mdf(C[TIMES].i, C[TIMES].v);
rev(Q[1].u, Q[1].v);
upd(LCA), ans[Q[1].id] = Ans, upd(LCA);
for(int i = 2; i <= cntq; ++i) {
while(TIMES < Q[i].t) ++TIMES, mdf(C[TIMES].i, C[TIMES].v);
while(TIMES > Q[i].t) mdf(C[TIMES].i, C[TIMES].u), --TIMES;
rev(Q[i-1].u, Q[i].u), rev(Q[i-1].v, Q[i].v), LCA = lca(Q[i].u, Q[i].v);
upd(LCA), ans[Q[i].id] = Ans, upd(LCA);
}
for(int i = 1; i <= cntq; ++i)
printf("%lld\n", ans[i]);
}