题目大意：给一棵$n$个节点的树，每个点有一个值$C_i$，每次询问一条路径$x->y$，求$sumlimits_{c}val_c imes sumlimits_{i=1}^{cnt_c}worth_i（cnt_c=sumlimits_{iin(x->y)}[C_i==c]）$。带修改
题解：树上带修莫队，在普通的树上莫队上加一维时间即可
卡点：$res$忘记开$long;long$
C++ Code：
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define N (maxn << 1)
#define bl(x) ((x) >> 11)
int n, m, l, r, p;
long long res;
long long ans[maxn];
int C[maxn], num[maxn];
long long W[maxn], V[maxn];
bool vis[maxn];
int Qcnt, Mcnt;
struct Query {
int l, r, tim, id, lca;
bool addlca;
inline bool operator < (const Query &rhs) const {
return (bl(l) == bl(rhs.l)) ? (bl(r) == bl(rhs.r) ? tim < rhs.tim : r < rhs.r) : l < rhs.l;
}
} q[maxn];
inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}
struct Modity {
int pos, C, tim;
inline void modify() {
if (vis[pos]) {
res -= W[num[::C[pos]]--] * V[::C[pos]];
res += W[++num[C]] * V[C];
}
swap(::C[pos], C);
}
} M[maxn];
int date[N], in[maxn], out[maxn], idx;
namespace tree {
int head[maxn], cnt;
struct Edge {
int to, nxt;
} e[maxn << 1];
void add(int a, int b) {
e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;
e[++cnt] = (Edge) {a, head[b]}; head[b] = cnt;
}
int fa[maxn];
void dfs(int u) {
date[in[u] = ++idx] = u;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa[u]) {
fa[v] = u;
dfs(v);
}
}
date[out[u] = ++idx] = u;
}
}
namespace tarjan {
int head[maxn], cnt;
struct QUERY {
int v, nxt, id;
} Q[maxn << 1];
void add(int a, int b, int c) {
Q[++cnt] = (QUERY) {b, head[a], c}; head[a] = cnt;
Q[++cnt] = (QUERY) {a, head[b], c}; head[b] = cnt;
}
int f[maxn];
void init(int n) {
for (int i = 1; i <= n; i++) f[i] = i;
}
int find(int x) {return (x == f[x] ? x : (f[x] = find(f[x])));}
void dfs(int u) {
for (int i = tree::head[u]; i; i = tree::e[i].nxt) {
int v = tree::e[i].to;
if (v != tree::fa[u]) {
dfs(v);
f[v] = find(u);
}
}
for (int i = head[u]; i; i = Q[i].nxt) q[Q[i].id].lca = find(Q[i].v);
}
}
#define ONLINE_JUDGE
#include <cctype>
namespace R {
int x;
#ifdef ONLINE_JUDGE
char *ch, op[1 << 26];
inline void init() {
fread(ch = op, 1, 1 << 26, stdin);
}
inline int read() {
while (isspace(*ch)) ch++;
for (x = *ch & 15, ch++; isdigit(*ch); ch++) x = x * 10 + (*ch & 15);
return x;
}
#else
char ch;
inline int read() {
ch = getchar();
while (isspace(ch)) ch = getchar();
for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
return x;
}
#endif
}
int O;
int main() {
#ifdef ONLINE_JUDGE
R::init();
#endif
tarjan::init(n = R::read()); m = R::read(), O = R::read();
for (int i = 1; i <= m; i++) V[i] = R::read();
for (int i = 1; i <= n; i++) W[i] = R::read();
for (int i = 1; i < n; i++) tree::add(R::read(), R::read());
tree::dfs(1);
for (int i = 1; i <= n; i++) C[i] = R::read();
for (int i = 1; i <= O; i++) {
if (R::read()) {
q[++Qcnt].tim = i;
tarjan::add(q[Qcnt].l = R::read(), q[Qcnt].r = R::read(), q[Qcnt].id = Qcnt);
} else M[++Mcnt].pos = R::read(), M[Mcnt].C = R::read(), M[Mcnt].tim = i;
}
tarjan::dfs(1);
for (int i = 1; i <= Qcnt; i++) {
int &l = q[i].l, &r = q[i].r;
if (in[l] > in[r]) swap(l, r);
l = (q[i].addlca = (q[i].lca != l)) ? out[l] : in[l];
r = in[r];
}
std::sort(q + 1, q + Qcnt + 1);
l = 1, r = 0, p = 0;
for (int i = 1; i <= Qcnt; i++) {
while (l > q[i].l) (vis[date[--l]] ^= 1) ? (res += W[++num[C[date[l]]]] * V[C[date[l]]]) : (res -= W[num[C[date[l]]]--] * V[C[date[l]]]);
while (r < q[i].r) (vis[date[++r]] ^= 1) ? (res += W[++num[C[date[r]]]] * V[C[date[r]]]) : (res -= W[num[C[date[r]]]--] * V[C[date[r]]]);
while (l < q[i].l) (vis[date[l]] ^= 1) ? (res += W[++num[C[date[l]]]] * V[C[date[l++]]]) : (res -= W[num[C[date[l]]]--] * V[C[date[l++]]]);
while (r > q[i].r) (vis[date[r]] ^= 1) ? (res += W[++num[C[date[r]]]] * V[C[date[r--]]]) : (res -= W[num[C[date[r]]]--] * V[C[date[r--]]]);
while (p < Mcnt && M[p + 1].tim < q[i].tim) M[++p].modify();
while (p && M[p].tim > q[i].tim) M[p--].modify();
ans[q[i].id] = res + (q[i].addlca ? W[num[C[q[i].lca]] + 1] * V[C[q[i].lca]] : 0);
}
for (int i = 1; i <= Qcnt; i++) printf("%lld
", ans[i]);
return 0;
}