树分块 树上莫队笔记 Mo's Algorithm on Tree

发表于2020-09-05更新于2023-09-17字数统计5k阅读时长53分作者Shane

参考博客：
莫队、带修莫队、树上莫队详解

树分块

这里介绍三种分块方法

  • 按 DFSDFS 序分块。严格保证块大小为 N\sqrt N，但是不保证直径，也不保证联通。处理子树信息比较方便。
  • 王室联邦分块。如果确定每个块大小至少为 N\sqrt N，可以保证分得每个块的大小和直径都不超过 3N3\sqrt N，但是不保证块联通。
  • 按深度分块。待补充…

这样分块是为了莫队的排序，使在两个查询间转移时只需进行 N\sqrt N 数量级的操作。

P2325 [SCOI2005]王室联邦

Description

题目链接

Solution

  • 构造方式：

    dfsdfs，同时创建一个栈存储未分块的节点。每 dfsdfs 到一个点时获取当前栈的大小，当搜完当前节点 nownow 的一个子节点后，判断栈的大小的增量是否大于等于 BB，是则将栈内所有新增点分到新的块中，并将首都点为当前节点 nownow，否则保留新增节点，处理下一个子节点。当当前节点的所有子节点都被搜过后，将当前节点入栈。dfsdfs 结束后将栈内所有剩余节点归入已经分好的最后一个块即可。

  • 证明：

    • 显然，每个块的大小 ∣S∣≥B|S| \ge B。

    • 由上述构造方式可知 nownow 的子节点 vv 对应子树中剩下的未被分块的节点个数小于 BB，而每次栈中剩下元素，即之前处理完的子树中未被分块的节点，其数目是小于 BB 的，故合并后得到的块的大小小于 2B2B。

    • dfsdfs 结束后，已经分好的块的大小都小于2B2B, 剩下的未分块的节点数小于 BB, 故最后一个块的大小小于 3B3B。

    • 综上可知，每个块大小在 [B,3B][B,3B] 之间，满足题目要求。

Code

王室联邦
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
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e3 + 5;

int n, b, ans, u, v;
int p[MAXN], pro[MAXN], belong[MAXN];

template <class T>
void read(T &x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct edge {
    int to, nxt;
} e[MAXN << 1];

void addEdge(int from, int to) {
    static int t;
    e[t].to = to, e[t].nxt = p[from], p[from] = t++;
}

stack<int> s;
void dfs(int now, int fa) {
    int tmp = s.size();
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to != fa) {
            dfs(to, now);
            if (s.size() - tmp >= b) {
                pro[++ans] = now;
                while (s.size() > tmp) {
                    int cur = s.top();
                    s.pop();
                    belong[cur] = ans;
                }
            }
        }
    }
    s.push(now);
}

int main() {
    read(n), read(b);
    fill(p, p + n + 1, -1);
    for (int i = 1; i <= n - 1; i++) {
        read(u), read(v);
        addEdge(u, v), addEdge(v, u);
    }
    dfs(1, 1);
    if (!ans) pro[++ans] = 1;
    while (!s.empty()) {
        int tmp = s.top();
        s.pop();
        belong[tmp] = ans;
    }
    printf("%d\n", ans);
    for (int i = 1; i <= n; i++) printf("%d ", belong[i]);
    printf("\n");
    for (int i = 1; i <= ans; i++) printf("%d ", pro[i]);
    return 0;
}

普通树上莫队

SP10707 COT2 - Count on a tree II

Description

题目链接

Solution1

采用王室联邦分块法。对于所有询问 {(ui,vi)}\{(u_i,v_i)\}，按 uiu_i 所属块编号从小到大排序，若 uiu_i 所属块相同按 viv_i 所属块编号从小到大排序。至于奇偶性优化…也许有点用，还是加上吧。

接下来考虑两个查询间如何转移。设 Su,vS_{u,v} 为路径 u−vu-v 上的所有点的集合，Tu,vT_{u,v}表示路径 u−vu-v 上的除 lca(u,v)lca(u,v) 外的点构成的集合。设上一次询问为 (u,v)(u,v)，本次询问为 (u′,v′)(u',v')。那么上一次询问涉及到的节点为 Su,v=Tu,v∪lca(u,v)S_{u,v}=T_{u,v}∪lca(u,v)，本次询问涉及到的节点为 Su′,v′=Tu′,v′∪lca(u′,v′)S_{u',v'}=T_{u',v'}∪lca(u',v')。定义 ⊕ 表示集合的对称差运算，由 ⊕ 的交换律和结合律，有：

Tu′,v′=Tu′,v′⊕Tu,v⊕Tv,uT_{u',v'}=T_{u',v'}⊕T_{u,v}⊕T_{v,u}

=(Su′,rt⊕Srt,v′)⊕(Su,rt⊕Srt,v)⊕Tu,v=(S_{u',rt}⊕S_{rt,v'})⊕(S_{u,rt}⊕S_{rt,v})⊕T_{u,v}

=(Su′,rt⊕Su,rt)⊕(Srt,v⊕Srt,v′)⊕Tu,v=(S_{u',rt}⊕S_{u,rt})⊕(S_{rt,v}⊕S_{rt,v'})⊕T_{u,v}

=Tu,u′⊕Tv,v′⊕Tu,v=T_{u,u'}⊕T_{v,v'}⊕T_{u,v}

=Tu,u′⊕Tv,v′⊕Su,v⊕lca(u,v)=T_{u,u'}⊕T_{v,v'}⊕S_{u,v}⊕lca(u,v)

=Su′,v′⊕lca(u′,v′)= S_{u',v'}⊕lca(u',v')

移项可得：Su′,v′=lca(u′,v′)⊕lca(u,v)⊕Tu,u′⊕Tv,v′⊕Su,vS_{u',v'}=lca(u',v')⊕lca(u,v)⊕T_{u,u'}⊕T_{v,v'}⊕S_{u,v}

求 lcalca 可用树链剖分(相比倍增常数小)，在 dfsdfs 分块时可顺便维护。
对于异或操作，可用一个数组记录每个节点是否在集合中。每更新一个节点，若其在集合中则将相应数值删除，否则加入集合。至于 Tu,u′T_{u,u'} 和 Tv,v′T_{v,v'}，分别直接遍历整个链，更新直至 lcalca 处停止即可。

Code1

Count on a tree II
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m, B, cntB, tot;
int val[MAXN], p[MAXN], belong[MAXN], ans[MAXN], cntC[MAXN];
int hson[MAXN], sz[MAXN], dep[MAXN], f[MAXN], top[MAXN];
bool vis[MAXN];
vector<int> v;

template <class T>
void read(T &x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Edge {
    int to, nxt;
} e[MAXN * 2];

struct Query {
    int x, y, id;
    friend bool operator<(const Query &a, const Query &b) {
        if (belong[a.x] == belong[b.x]) {
            if (belong[a.x] & 1) return belong[a.y] < belong[b.y];
            return belong[a.y] > belong[b.y];
        }
        return belong[a.x] < belong[b.x];
    }
} q[MAXN * 3];

void addEdge(int from, int to) {
    static int t;
    e[t].to = to, e[t].nxt = p[from], p[from] = t++;
}

stack<int> s;
void dfs(int now, int fa) {
    sz[now] = 1, dep[now] = dep[fa] + 1, f[now] = fa;
    int tmp = s.size();
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to != fa) {
            dfs(to, now);
            sz[now] += sz[to];
            if (!hson[now] || sz[to] > sz[hson[now]]) hson[now] = to;
            if (s.size() - tmp >= B) {
                cntB++;
                while (s.size() > tmp) {
                    int cur = s.top();
                    s.pop();
                    belong[cur] = cntB;
                }
            }
        }
    }
    s.push(now);
}

void dfs2(int now, int tp) {
    top[now] = tp;
    if (!hson[now]) return;
    dfs2(hson[now], tp);
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to != f[now] && to != hson[now]) dfs2(to, to);
    }
}

int lca(int u, int v) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    while (top[u] != top[v]) {
        u = f[top[u]];
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
    }
    if (dep[u] < dep[v]) swap(u, v);
    return v;
}

void getBlock() {
    B = sqrt(n);
    dfs(1, 1);
    dfs2(1, 1);
    if (!cntB) ++cntB;
    while (!s.empty()) {
        int tmp = s.top();
        s.pop();
        belong[tmp] = cntB;
    }
}

void discretize() {
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; i++)
        val[i] = lower_bound(v.begin(), v.end(), val[i]) - v.begin() + 1;
}

void modify(int now) {
    if (!vis[now]) {
        ++cntC[val[now]];
        if (cntC[val[now]] == 1) tot++;
    } else {
        --cntC[val[now]];
        if (cntC[val[now]] == 0) tot--;
    }
    vis[now] ^= 1;
}

void update(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    while (dep[u] > dep[v]) modify(u), u = f[u];
    while (u != v) modify(u), modify(v), u = f[u], v = f[v];
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(val[i]), v.push_back(val[i]);
    discretize();
    fill(p + 1, p + n + 1, -1);
    int x(0), y(0);
    for (int i = 1; i <= n - 1; i++) {
        read(x), read(y);
        addEdge(x, y), addEdge(y, x);
    }
    getBlock();
    for (int i = 1; i <= m; i++) {
        read(q[i].x), read(q[i].y);
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    x = 1, y = 1;
    modify(1);
    for (int i = 1; i <= m; i++) {
        int lca1 = lca(x, y), lca2 = lca(q[i].x, q[i].y);
        update(x, q[i].x), x = q[i].x;
        update(y, q[i].y), y = q[i].y;
        modify(lca1), modify(lca2);
        ans[q[i].id] = tot;
    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

Solution2

考虑把树上的问题转化到序列上。

这里引入欧拉序，它的思想是：当访问到点ii 时，加入序列，记录时间戳 in[i]in[i]，然后访问 ii 的子树，当访问完时，再把 ii 加入序列，并记录时间戳 out[i]out[i]。如果将一条链映射到序列中的一段区间，那么这个区间中出现两次的节点一定不属于这条链（两端点的 lcalca）除外, 这样只需要统计出现一次的节点即可。

对于一条链 (u,v)(u,v)，设 in[u]<in[v]in[u]<in[v]，讨论两种情况：

  • lca(u,v)=ulca(u,v)=u，统计欧拉序在 [in[u],in[v]][in[u],in[v]] 的节点即可。
  • lca(u,v)≠ulca(u,v)\neq u，统计欧拉序在 [out[u],in[v]][out[u],in[v]] 的节点，同时加上 lca(u,v)lca(u,v) 即可。

注：

  • 这里求 lcalca 依然使用树链剖分。
  • 对于上述第二种情况，不取 [in[u],in[v]][in[u],in[v]] 是因为这样会导致 uu 在序列中出现两次。另外， (in[u],out[u])(in[u],out[u]) 间的节点在 uu 的子树中，这些节点显然没有必要统计。
  • 分块时需要注意序列长度为 2n2n。

Code2

Count on a tree II
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m, B, tot;
int val[MAXN], p[MAXN], in[MAXN], out[MAXN], from[MAXN * 2];
int belong[MAXN * 2], ans[MAXN], cntC[MAXN];
int hson[MAXN], sz[MAXN], dep[MAXN], f[MAXN], top[MAXN];
bool vis[MAXN];
vector<int> v;

template <class T>
void read(T &x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Edge {
    int to, nxt;
} e[MAXN * 2];

struct Query {
    int l, r, id, lca;
    friend bool operator<(const Query &a, const Query &b) {
        if (belong[a.l] == belong[b.l]) {
            if (belong[a.l] & 1) return belong[a.r] < belong[b.r];
            return belong[a.r] > belong[b.r];
        }
        return belong[a.l] < belong[b.l];
    }
} q[MAXN * 3];

void addEdge(int from, int to) {
    static int t;
    e[t].to = to, e[t].nxt = p[from], p[from] = t++;
}

void dfs(int now, int fa) {
    static int tim = 1;
    in[now] = tim, from[tim++] = now;
    sz[now] = 1, dep[now] = dep[fa] + 1, f[now] = fa;
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to != fa) {
            dfs(to, now);
            sz[now] += sz[to];
            if (!hson[now] || sz[to] > sz[hson[now]]) hson[now] = to;
        }
    }
    out[now] = tim, from[tim++] = now;
}

void dfs2(int now, int tp) {
    top[now] = tp;
    if (!hson[now]) return;
    dfs2(hson[now], tp);
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to != f[now] && to != hson[now]) dfs2(to, to);
    }
}

int lca(int u, int v) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    while (top[u] != top[v]) {
        u = f[top[u]];
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
    }
    if (dep[u] < dep[v]) swap(u, v);
    return v;
}

void discretize() {
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; i++)
        val[i] = lower_bound(v.begin(), v.end(), val[i]) - v.begin() + 1;
}

void modify(int now) {
    if (!vis[now]) {
        ++cntC[val[now]];
        if (cntC[val[now]] == 1) tot++;
    } else {
        --cntC[val[now]];
        if (cntC[val[now]] == 0) tot--;
    }
    vis[now] ^= 1;
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(val[i]), v.push_back(val[i]);
    discretize();
    fill(p + 1, p + n + 1, -1);
    int x(0), y(0);
    for (int i = 1; i <= n - 1; i++) {
        read(x), read(y);
        addEdge(x, y), addEdge(y, x);
    }
    B = max(1, 2 * n / (int)sqrt(m));
    dfs(1, 1), dfs2(1, 1);
    for (int i = 1; i <= m; i++) {
        read(x), read(y);
        if (in[x] > in[y]) swap(x, y);
        q[i].lca = lca(x, y);
        if (q[i].lca == x) {
            q[i].l = in[x];
            q[i].r = in[y];
            q[i].lca = 0;
        } else {
            q[i].l = out[x];
            q[i].r = in[y];
        }
        q[i].id = i;
    }
    for (int i = 1; i <= 2 * n; i++) belong[i] = (i - 1) / B + 1;
    sort(q + 1, q + m + 1);
    x = 1, y = 0;
    for (int i = 1; i <= m; i++) {
        while (x < q[i].l) modify(from[x++]);
        while (x > q[i].l) modify(from[--x]);
        while (y > q[i].r) modify(from[y--]);
        while (y < q[i].r) modify(from[++y]);
        if (q[i].lca) modify(q[i].lca);
        ans[q[i].id] = tot;
        if (q[i].lca) modify(q[i].lca);
    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

注：本题有在线做法，以后有空再补上。

树上带修莫队

处理方法和序列上的莫队相同，对每个询问增加一维时间。

P4074 [WC2013]糖果公园

Description

题目链接

Hint

记录每个询问之前的修改次数，排序的时候以修改次数为第三关键字排序即可。查询的时候，如果多修改了则回退，否则对未修改的部分进行修改，当修改位置在本次查询区间内时对答案进行更新。

Solution1

求欧拉序后转化为区间问题。

Code1

糖果公园（欧拉序）
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 5;
int n, m, Q, B, type, cntQ, cntR;
int C[MAXN], V[MAXN], W[MAXN];
ll tot, ans[MAXN];
int p[MAXN], in[MAXN], out[MAXN], from[MAXN * 2];
int belong[MAXN * 2], cntC[MAXN];
int hson[MAXN], sz[MAXN], dep[MAXN], f[MAXN], top[MAXN];
bool vis[MAXN];

template <class T>
void read(T &x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Edge {
    int to, nxt;
} e[MAXN * 2];

struct Query {
    int l, r, id, lca, t;
    friend bool operator<(const Query &a, const Query &b) {
        if (belong[a.l] == belong[b.l]) {
            if (belong[a.r] == belong[b.r]) return a.t < b.t;
            if (belong[a.l] & 1) return belong[a.r] < belong[b.r];
            return belong[a.r] > belong[b.r];
        }
        return belong[a.l] < belong[b.l];
    }
} q[MAXN];

struct Replace {
    int id, type;
} r[MAXN];

void addEdge(int from, int to) {
    static int t;
    e[t].to = to, e[t].nxt = p[from], p[from] = t++;
}

void dfs(int now, int fa) {
    static int tim = 1;
    in[now] = tim, from[tim++] = now;
    sz[now] = 1, dep[now] = dep[fa] + 1, f[now] = fa;
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to != fa) {
            dfs(to, now);
            sz[now] += sz[to];
            if (!hson[now] || sz[to] > sz[hson[now]]) hson[now] = to;
        }
    }
    out[now] = tim, from[tim++] = now;
}

void dfs2(int now, int tp) {
    top[now] = tp;
    if (!hson[now]) return;
    dfs2(hson[now], tp);
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to != f[now] && to != hson[now]) dfs2(to, to);
    }
}

int lca(int u, int v) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    while (top[u] != top[v]) {
        u = f[top[u]];
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
    }
    if (dep[u] < dep[v]) swap(u, v);
    return v;
}

void modify(int now) {
    if (!vis[now]) {
        ++cntC[C[now]];
        tot += 1ll * W[cntC[C[now]]] * V[C[now]];
    } else {
        tot -= 1ll * W[cntC[C[now]]] * V[C[now]];
        --cntC[C[now]];
    }
    vis[now] ^= 1;
}

void change(Replace &rep) {
    if (vis[rep.id]) {
        modify(rep.id);
        swap(rep.type, C[rep.id]);
        modify(rep.id);
    } else
        swap(rep.type, C[rep.id]);
}

int main() {
    read(n), read(m), read(Q);
    fill(p + 1, p + n + 1, -1);
    for (int i = 1; i <= m; i++) read(V[i]);
    for (int i = 1; i <= n; i++) read(W[i]);
    int x, y, t;
    for (int i = 1; i <= n - 1; i++) {
        read(x), read(y);
        addEdge(x, y), addEdge(y, x);
    }
    for (int i = 1; i <= n; i++) read(C[i]);
    B = pow(n, 2.0 / 3);  //不要忘了.0!
    dfs(1, 1), dfs2(1, 1);
    for (int i = 1; i <= Q; i++) {
        read(type);
        if (type == 1) {
            cntQ++;
            read(x), read(y);
            if (in[x] > in[y]) swap(x, y);
            q[cntQ].lca = lca(x, y);
            if (q[cntQ].lca == x) {
                q[cntQ].l = in[x];
                q[cntQ].r = in[y];
                q[cntQ].lca = 0;
            } else {
                q[cntQ].l = out[x];
                q[cntQ].r = in[y];
            }
            q[cntQ].id = cntQ;
            q[cntQ].t = cntR;
        } else {
            cntR++;
            read(x), read(y);
            r[cntR].id = x, r[cntR].type = y;
        }
    }
    for (int i = 1; i <= 2 * n; i++) belong[i] = (i - 1) / B + 1;
    sort(q + 1, q + cntQ + 1);
    x = 1, y = 0, t = 0;
    for (int i = 1; i <= cntQ; i++) {
        while (x < q[i].l) modify(from[x++]);
        while (x > q[i].l) modify(from[--x]);
        while (y > q[i].r) modify(from[y--]);
        while (y < q[i].r) modify(from[++y]);
        while (t < q[i].t) change(r[++t]);
        while (t > q[i].t) change(r[t--]);
        if (q[i].lca) modify(q[i].lca);
        ans[q[i].id] = tot;
        if (q[i].lca) modify(q[i].lca);
    }
    for (int i = 1; i <= cntQ; i++) printf("%lld\n", ans[i]);
    return 0;
}

Solution2

采用王室联邦分块法。也许是我写假了，跑得巨慢…

Code2

糖果公园(王室联邦分块)
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 5;
int n, m, Q, B, type, cntQ, cntR, cntB;
int C[MAXN], V[MAXN], W[MAXN];
ll tot, ans[MAXN];
int p[MAXN];
int belong[MAXN], cntC[MAXN];
int hson[MAXN], sz[MAXN], dep[MAXN], f[MAXN], top[MAXN];
bool vis[MAXN];

template <class T>
void read(T &x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Edge {
    int to, nxt;
} e[MAXN * 2];

struct Query {
    int x, y, id, t;
    friend bool operator<(const Query &a, const Query &b) {
        if (belong[a.x] == belong[b.x]) {
            if (belong[a.y] == belong[b.y]) return a.t < b.t;
            if (belong[a.x] & 1) return belong[a.y] < belong[b.y];
            return belong[a.y] > belong[b.y];
        }
        return belong[a.x] < belong[b.x];
    }
} q[MAXN];

struct Replace {
    int id, type;
} r[MAXN];

void addEdge(int from, int to) {
    static int t;
    e[t].to = to, e[t].nxt = p[from], p[from] = t++;
}

stack<int> s;
void dfs(int now, int fa) {
    sz[now] = 1, dep[now] = dep[fa] + 1, f[now] = fa;
    int tmp = s.size();
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to != fa) {
            dfs(to, now);
            sz[now] += sz[to];
            if (!hson[now] || sz[to] > sz[hson[now]]) hson[now] = to;
            if (s.size() - tmp >= B) {
                cntB++;
                while (s.size() > tmp) {
                    int cur = s.top();
                    s.pop();
                    belong[cur] = cntB;
                }
            }
        }
    }
    s.push(now);
}

void dfs2(int now, int tp) {
    top[now] = tp;
    if (!hson[now]) return;
    dfs2(hson[now], tp);
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to != f[now] && to != hson[now]) dfs2(to, to);
    }
}

int lca(int u, int v) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    while (top[u] != top[v]) {
        u = f[top[u]];
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
    }
    if (dep[u] < dep[v]) swap(u, v);
    return v;
}

void getBlock() {
    B = sqrt(n);
    dfs(1, 1);
    dfs2(1, 1);
    if (!cntB) ++cntB;
    while (!s.empty()) {
        int tmp = s.top();
        s.pop();
        belong[tmp] = cntB;
    }
}

void modify(int now) {
    if (!vis[now]) {
        ++cntC[C[now]];
        tot += 1ll * W[cntC[C[now]]] * V[C[now]];
    } else {
        tot -= 1ll * W[cntC[C[now]]] * V[C[now]];
        --cntC[C[now]];
    }
    vis[now] ^= 1;
}

void update(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    while (dep[u] > dep[v]) modify(u), u = f[u];
    while (u != v) modify(u), modify(v), u = f[u], v = f[v];
}

void change(Replace &rep) {
    if (vis[rep.id]) {
        modify(rep.id);
        swap(rep.type, C[rep.id]);
        modify(rep.id);
    } else
        swap(rep.type, C[rep.id]);
}

int main() {
    read(n), read(m), read(Q);
    fill(p + 1, p + n + 1, -1);
    for (int i = 1; i <= m; i++) read(V[i]);
    for (int i = 1; i <= n; i++) read(W[i]);
    int x, y, t;
    for (int i = 1; i <= n - 1; i++) {
        read(x), read(y);
        addEdge(x, y), addEdge(y, x);
    }
    for (int i = 1; i <= n; i++) read(C[i]);
    B = pow(n, 2.0 / 3);
    getBlock();
    for (int i = 1; i <= Q; i++) {
        read(type);
        if (type == 1) {
            cntQ++;
            read(x), read(y);
            q[cntQ].x = x, q[cntQ].y = y;
            q[cntQ].id = cntQ;
            q[cntQ].t = cntR;
        } else {
            cntR++;
            read(x), read(y);
            r[cntR].id = x, r[cntR].type = y;
        }
    }
    sort(q + 1, q + cntQ + 1);
    x = 1, y = 1, t = 0;
    modify(1);
    for (int i = 1; i <= cntQ; i++) {
        int lca1 = lca(x, y), lca2 = lca(q[i].x, q[i].y);
        update(x, q[i].x), x = q[i].x;
        update(y, q[i].y), y = q[i].y;
        modify(lca1), modify(lca2);
        while (t < q[i].t) change(r[++t]);
        while (t > q[i].t) change(r[t--]);
        ans[q[i].id] = tot;
    }
    for (int i = 1; i <= cntQ; i++) printf("%lld\n", ans[i]);
    return 0;
}