P4074 WC2013糖果公园
树上带修莫队（欧拉序分块，特判lca），然后，，，我排序错了，T了一页。。。
为了过都没用递归。。。修改就按他说的修改就行。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6+10;
ll N, M, seq[MAXN], Q, head[MAXN], cnt = -1, C[MAXN], V[MAXN], W[MAXN], block[MAXN], tst[MAXN], tem[MAXN];
ll in[MAXN], out[MAXN], num, dep[MAXN], fa[22][MAXN], tim, chacnt, len, tot, pos[2][MAXN], vis[MAXN];
ll SIZ;
struct edg {ll nt, to;} E[MAXN];
struct ask {
ll x, y, id, flag, la;
friend bool operator < (ask a, ask b) {return block[a.x] == block[b.x] ? block[a.y] == block[b.y] ? a.id < b.id : block[a.y] < block[b.y] : block[a.x] < block[b.x];}
} A[MAXN];
struct cha {ll x, y, tim;} CH[MAXN];
void add(ll, ll);
void dfs(ll, ll);
ll lca(ll, ll);
int main() {
//freopen("P4074_1.in", "r", stdin);
memset(head, -1, sizeof(head));
scanf("%lld%lld%lld", &N, &M, &Q);
SIZ = (ll)pow(N, 2.0 / 3.0);
for (ll i = 1; i <= M; i++) scanf("%lld", V+i);
for (ll i = 1; i <= N; i++) scanf("%lld", W+i);
for (ll i = 1, x, y; i < N; i++) scanf("%lld%lld", &x, &y),add(x, y),add(y, x);
for (ll i = 1; i <= N; i++) scanf("%lld", C+i);
dfs(1, 0);
for (ll i = 1, kind, x, y; i <= Q; i++) {
scanf("%lld%lld%lld", &kind, &x, &y);
if (kind) {
if (in[x] > in[y]) swap(x, y);
if (lca(x, y) == x) tim++, A[tim] = {pos[0][x], pos[0][y], tim, 0, 0};
else tim++, A[tim] = {pos[1][x], pos[0][y], tim, 1, lca(x, y)};
} else CH[++chacnt] = {x, y, tim};
}
for (ll i = 1; i <= 2*N; i++) {
if (i % SIZ == 1) tot++;
block[i] = tot;
}
ll now = 0, ans = 0, l = 1, r = 0; sort(A+1, A+tim+1); CH[chacnt+1].tim = 0x3f3f3f3f3f3f3f3f;
for (ll i = 1; i <= tim; i++) {
while (CH[now].tim < A[i].id && now <= chacnt) {
now++;
if (vis[CH[now].x] == 1) ans -= (V[C[CH[now].x]] * W[tst[C[CH[now].x]]--]);
swap(CH[now].y, C[CH[now].x]);
if (vis[CH[now].x] == 1) ans += (V[C[CH[now].x]] * W[++tst[C[CH[now].x]]]);
}
while (A[i].id <= CH[now].tim && now >= 1) {
if (vis[CH[now].x] == 1) ans -= (V[C[CH[now].x]] * W[tst[C[CH[now].x]]--]);
swap(CH[now].y, C[CH[now].x]);
if (vis[CH[now].x] == 1) ans += (V[C[CH[now].x]] * W[++tst[C[CH[now].x]]]);
now--;
}
while (r < A[i].y) {
r++, vis[seq[r]]++;
if (vis[seq[r]] == 1) ans += (V[C[seq[r]]] * W[++tst[C[seq[r]]]]);
else ans -= (V[C[seq[r]]] * W[tst[C[seq[r]]]--]);
}
while (l > A[i].x) {
l--, vis[seq[l]]++;
if (vis[seq[l]] == 1) ans += (V[C[seq[l]]] * W[++tst[C[seq[l]]]]);
else ans -= (V[C[seq[l]]] * W[tst[C[seq[l]]]--]);
}
while (l < A[i].x) {
vis[seq[l]]--;
if (vis[seq[l]] == 1) ans += (V[C[seq[l]]] * W[++tst[C[seq[l]]]]);
else ans -= (V[C[seq[l]]] * W[tst[C[seq[l]]]--]);
l++;
}
while (r > A[i].y) {
vis[seq[r]]--;
if (vis[seq[r]] == 1) ans += (V[C[seq[r]]] * W[++tst[C[seq[r]]]]);
else ans -= (V[C[seq[r]]] * W[tst[C[seq[r]]]--]);
r--;
}
if (A[i].flag) {
vis[A[i].la]++;
if (vis[A[i].la] == 1) ans += (V[C[A[i].la]] * W[++tst[C[A[i].la]]]);
else ans -= (V[C[A[i].la]] * W[tst[C[A[i].la]]--]);
}
tem[A[i].id] = ans;
if (A[i].flag) {
vis[A[i].la]--;
if (vis[A[i].la] == 1) ans += (V[C[A[i].la]] * W[++tst[C[A[i].la]]]);
else ans -= (V[C[A[i].la]] * W[tst[C[A[i].la]]--]);
}
}
for (ll i = 1; i <= tim; i++) printf("%lld
", tem[i]);
return 0;
}
void add(ll x, ll y) {E[++cnt] = {head[x], y};head[x] = cnt;}
void dfs(ll n, ll ff) {
in[n] = ++num, fa[0][n] = ff, seq[++len] = n, pos[0][n] = len;
for (ll i = 1; i <= 20; i++) fa[i][n] = fa[i-1][fa[i-1][n]];
for (ll i = head[n]; ~i; i = E[i].nt) {
if (E[i].to == ff) continue;
else dep[E[i].to] = dep[n] + 1, dfs(E[i].to, n);
}
out[n] = num, seq[++len] = n, pos[1][n] = len;
}
ll lca(ll x, ll y) {
if (dep[x] < dep[y]) swap(x, y);
ll dis = dep[x] - dep[y];
for (ll i = 20; ~i; i--) if ((dis >> i) & 1) x = fa[i][x];
if (x == y) return x;
for (ll i = 20; ~i; i--) if (fa[i][x] != fa[i][y]) x = fa[i][x], y = fa[i][y];
return fa[0][x];
}