前年生日的飞雪。
重链剖分。
简单来说，树链剖分就是将一棵树剖分成多个连续的段，进而映射到线性的序列上以使用数据结构进行维护的一种方法。
1. 重链剖分
1.1 基本定义
- 重儿子：非叶子节点的子节点中，子树节点数最多的那个子节点。
- 轻儿子：非叶子节点的子节点中，非重儿子的所有节点。
- 重边：连接任意两个重儿子的边。
- 轻边：非重边的所有边。
- 重链：一条均为重边的链。
- dfs 序：访问的顺序。即点映射到序列的编号。
1.2 基本操作
重链剖分将一棵树完全地剖分，且每个点都 属于且仅属于 一条重链（这条链可能长度为 $0$），将这一点与重儿子区别开来。由两个基础的 dfs 组成。
1.2.1 dfs1
第一层的 dfs 维护了树上各节点的基本信息，包括子树节点数量（包含自己）$sz_i$、节点深度 $dep_i$、父节点 $fa_i$、重儿子编号 $son_i$。具体见下。
1
2
3
4
5
6
7
8
9
10
11
|
void dfs1 (int x, int f) {
fa[x] = f;
siz[x] = 1;
dep[x] = dep[f] + 1;
for (auto v : g[x]) {
if (v == f) continue;
dfs (v, x);
siz[x] += siz[v];
if (siz[ son[x] ] < siz[v]) son[x] = v;
}
}
|
1.2.2 dfs2
第二层的 dfs 维护了各节点进行树剖的核心信息：节点映射到序列上的编号 $nid_u$、节点所处重链（若不在则链头为自己）的链头 $tp_u$。维护重儿子的目的是先便利重边使重儿子段连续。因此遍历到点 $u$ 时，我们先确定是否为叶子节点，若非则优先遍历重儿子。后遍历其余子节点 $v$ 时，由于 $(u,v)$ 边一定不是重边，故链头设为其本身。
1
2
3
4
5
6
7
8
9
|
void dfs2 (int x, int top) {
nid[x] = ++ col;
tp[x] = top;
w[col] = a[x];
if (son[x]) dfs2 (son[x], top);
for (auto v : g[x])
if (!nid[v])
dfs2 (v, v);
}
|
3. 性质
- 重链的 dfs 序是 连续 的。
- 走轻边，子树大小 至少减少 $\dfrac 12$。
- 树任意两点间路径由不超过 $\log n$ 条 重链 组成。
- 任意一点到根的 轻边 数量不超过 $\log n$。
4. 复杂度分析
对于当前节点，我们下一步跳的要么是 重边，要么是 轻边。前面已经提到，重边一定处于连续的一段中，且终点向下必为轻边或者为叶子节点。故直接讨论轻边。
由于重儿子的子树大小是不小于当前节点的，又因兄弟节点（即同级轻儿子）可能有许多，故当前点的子树大小是其父节点的至多二分之一，因此每次向下跳节点数至少会减少 $\dfrac12$，因此总体跳的复杂度为 $\mathcal O(\log n)$。
3. 基本应用
在线查询两点的 LCA。
下面介绍查询操作。
树剖的 LCA 与倍增 LCA 类似，都是两点不段向上跳的过程。
对于两个不同的点 $x$，$y$，如果两点的链头相同时，则深度更小的那个点即为答案。否则，我们比较两点链头的深度。我们假设要跳 $x$ 点。如果点 $x$ 的链头深度比 $y$ 链头更深，那么需要优先选择 $x$ 向上跳（如若不这样，LCA 将一直返回根节点。）。直至 $tp_x=tp_y$，LCA 即为深度更浅的那个点。
1
2
3
4
5
6
7
|
int lca (int x, int y) {
while (tp[x] != tp[y]) {
if (dep[ tp[x] ] < dep[ tp[y] ]) swap (x, y);
x = fa[ tp[x] ];
}
return dep[x] > dep[y] ? y : x;
}
|
5. 例题
这道题即为我们上文所写的用数据结构来维护映射后的序列的具体应用。
规定：本题题解的
modify(x,l,r,k) 是线段树区间加操作。
query(x,l,r) 函数是线段树区间求和操作。
路径加操作
操作与求 LCA 过程无异。设当前跳的点为 $x$，由于重链上编号连续，且自链头到底编号递增，故 $[id_{tp_x},id_x]$ 整体加上 $k$。之后继续往上跳，直至 $tp_x=tp_y$。最后将 $[id_x,id_y]$（不妨使 $x$ 的深度小于 $y$）加上 $k$，即可完成路径加操作。
1
2
3
4
5
6
7
8
9
|
void pathChange (int x, int y, ll k) {
while (tp[x] != tp[y]) {
if (dep[ tp[x] ] < dep[ tp[y] ]) swap (x, y);
modify (1, nid[ tp[x] ], nid[x], k);
x = fa[ tp[x] ];
}
if (dep[x] > dep[y]) swap (x, y);
modify (1, nid[x], nid[y], k);
}
|
路径查询
与上类似。
1
2
3
4
5
6
7
8
9
10
11
|
ll pathQuery (int x, int y) {
ll ret = 0;
while (tp[x] != tp[y]) {
if (dep[ tp[x] ] < dep[ tp[y] ]) swap (x, y);
ret = (ret + query (1, nid[ tp[x] ], nid[x])) % p;
x = fa[ tp[x] ];
}
if (dep[x] > dep[y]) swap (x, y);
ret = (ret + query (1, nid[x], nid[y])) % p;
return ret;
}
|
子树修改
由于优先遍历的特性，一个节点 $u$ 及其所有子节点的编号构成的集合必定为 ${id_u,id_u+1,\cdots,id_u+sz_u-1}$，因此映射到序列上可看作是将这段区间整体加 $k$。代码也非常简单，如下。
1
|
modify (1,nid[x],nid[x] + sz[x] - 1, k);
|
子树查询
与上类似。
1
|
query (1,nid[x],nid[x] + sz[x] - 1);
|
$Q$ 次询问，每次询问查询 $\sum\limits_{i=l}^r[\operatorname{Depth}(\operatorname{LCA}(i,z))]$。
考虑转换这个关系。
我们不妨将 $[l,r]$ 中点到根节点的最短路径上所有点的点权都加 $1$，那么所查询即为 $1\to z$ 的点权之和。（考虑每个点对于答案的贡献，那么根据 LCA 的定义，只有两个点到根节点的公共路径上的点才有可能做出贡献，而这段公共路径的大小即为 LCA 的深度大小，因此可以如此转换）
但是这样还是不好做，怎么办？
离线！
对于每个点显然有 $ans[l,r]=ans[0,r]-ans[0,l-1]$，因此我们将每段查询区间视作两点：$l-1$ 与 $r$。加入离线队列，并按照此为序，每次新增就在树上进行路径加操作。遇到类型 $l-1$ 的点，就将答案减去当前查询 $1\to z$ 的路径和；遇到类型 $r$ 的点，就将答案加上当前查询 $1\to z$ 的路径和。
复杂度 $\mathcal O(n\log^2 n)$。
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
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 <vector>
#include <iostream>
#include <algorithm>
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const int MAXN = 50010;
const int MOD = 201314;
struct SegmenTree {
int l, r;
int sum, lazy, siz;
} seg[MAXN << 2];
void pushup (int x) {
seg[x].sum = seg[ls].sum + seg[rs].sum;
}
void pushdown (int x) {
int& k = seg[x].lazy;
if (k) {
seg[ls].sum += seg[ls].siz * k;
seg[rs].sum += seg[rs].siz * k;
seg[ls].lazy += k;
seg[rs].lazy += k;
seg[ls].lazy %= MOD; seg[ls].sum %= MOD;
seg[rs].lazy %= MOD; seg[rs].sum %= MOD;
k = 0;
}
}
void build (int x, int l, int r) {
seg[x].l = l, seg[x].r = r;
seg[x].siz = r - l + 1;
seg[x].lazy = seg[x].sum = 0;
if (l == r) return ;
int mid = (l + r) >> 1;
build (ls, l, mid);
build (rs, mid + 1, r);
}
void upd (int x, int l, int r, int k) {
if (l > seg[x].r || r < seg[x].l) return ;
if (seg[x].l >= l && seg[x].r <= r) {
seg[x].sum += seg[x].siz * k;
seg[x].lazy += k;
return ;
}
pushdown (x);
upd (ls, l, r, k);
upd (rs, l, r, k);
pushup (x);
}
int query (int x, int l, int r) {
if (l > seg[x].r || r < seg[x].l) return 0;
if (seg[x].l >= l && seg[x].r <= r) return seg[x].sum % MOD;
pushdown (x);
return ( query (ls, l, r) + query (rs, l, r) ) % MOD;
}
struct quest {
int pos, z, i, k;
bool operator < (const quest& rhs) const {
return pos < rhs.pos;
}
};
int n, m;
int fa[MAXN];
vector <int> e[MAXN];
int dep[MAXN], siz[MAXN], son[MAXN];
void dfs1 (int x) {
dep[x] = dep[ fa[x] ] + 1;
siz[x] = 1;
int maxson = -1;
for (auto to : e[x]) {
if (fa[x] == to) continue ;
dfs1 (to);
siz[x] += siz[to];
if (siz[to] > maxson) maxson = siz[to], son[x] = to;
}
}
int tp[MAXN], id[MAXN], cnt;
void dfs2 (int x, int Top) {
id[x] = ++ cnt;
tp[x] = Top;
if (!son[x]) return ;
dfs2 (son[x], Top);
for (auto to : e[x])
if (!id[to])
dfs2 (to, to);
}
void rupd (int x, int y, int k) {
while (tp[x] != tp[y]) {
if (dep[ tp[x] ] < dep[ tp[y] ]) swap (x, y);
upd (1, id[ tp[x] ], id[x], 1);
x = fa[ tp[x] ];
}
if (dep[x] > dep[y]) swap (x, y);
upd (1, id[x], id[y], 1);
}
int qsum (int x, int y) {
int ans = 0;
while (tp[x] != tp[y]) {
if (dep[ tp[x] ] < dep[ tp[y] ]) swap (x, y);
ans += query (1, id[ tp[x] ], id[x]);
ans %= MOD;
x = fa[ tp[x] ];
}
if (dep[x] > dep[y]) swap (x, y);
ans += query (1, id[x], id[y]);
return (ans + MOD) % MOD;
}
int ans[MAXN];
int main (void) {
scanf ("%d%d", &n, &m);
for (int i = 2; i <= n; i++) {
scanf ("%d", &fa[i]);
++ fa[i];
e[ fa[i] ].push_back (i);
e[i].push_back (fa[i]);
}
dfs1 (1);
dfs2 (1, 1);
vector <quest> queries;
for (int i = 1; i <= m; i ++) {
int l, r, z;
scanf ("%d%d%d", &l, &r, &z);
l ++ , r ++, z ++;
queries.push_back ({l - 1, z, i, -1});
queries.push_back ({r, z, i, 1});
}
sort (queries.begin (), queries.end () );
build (1, 1, n);
int cur = 0;
for (auto q : queries) {
while (cur < q.pos) rupd (1, ++ cur, 1);
ans[q.i] += q.k * qsum (1, q.z);
ans[q.i] = (ans[q.i] + MOD) % MOD;
}
for (int i = 1; i <= m; i ++)
printf ("%d\n", ans[i]);
return 0;
}
|
$Q$ 次询问，每次询问查询 $\sum\limits_{i=1}^r[\operatorname{Depth}(\operatorname{LCA}(i,z)]^k$，$k$ 为给定常数。
上一道题的加强版。
我们仍然考虑上道题的 Trick。
我们这样进行路径加的实质其实是树上差分，即若 $u$，$v$ 两点的 LCA 为 $w$，那么 $w$ 点的贡献 $p_w=\sum\limits_{a\in1\to w}p_a=\sum\limits_{a\in1\to w}1=\sum\limits_{a\in1\to w}[(\operatorname{Depth}(a)+1)^1-\operatorname{Depth}(a)^1]$。
而将指数拓展到 $k$ 的情况，为了保持差分的性质，我们只需更改为 $\sum\limits_{a\in1\to w}[(\operatorname{Depth}(a)+1)^k-\operatorname{Depth}(a)^k$，便可转化为上一道题了。也就是说，在维护路径时，对于路径上每个点 $a$，加上 $(\operatorname{Depth}(a)+1)^k-\operatorname{Depth}(a)^k$。
Code
没 fix，和上题差不多，改一下线段树区间加操作就好了。
查询给定树修改某个点的权值后的最大权独立集的权值大小，$Q\le10^5$ 次。
这道题就是 P1352 没有上司的舞会
一题的带修版。我们考虑这道题的转移式。设 $f_{i,1/0}$ 表示以 $i$ 为根，选/不选点 $i$ 的答案，$a_i$ 为 $i$ 的权值。显然有 $f_{i,1}=a_i+\sum\limits_{u\in son_i}f_{u,0}$，$f_{i,0}=\sum\limits_{u\in}\max{f_{u,0},f_{u,1}}$。很简单。
那带上修改该怎么做？
我们仍然设 $f_{i,1/0}$ 表示以 $i$ 为根，选/不选点 $i$ 的答案。再设 $g_{i,1/0}$ 表示以 $i$ 为根，选/不选点 $i$ 的答案（且不选重儿子）。设 $v$ 是节点 $i$ 的重儿子，我们有：
$$g_{i,0}=\sum\limits_{u\in son_i\and u\not=v}\max{f_{u,0},f_{i,1}}\ g_{i,1}=a_i+\sum\limits_{u\in son_i\and u\not=v}\max{f_{u,0},f_{i,1}}\f_{i,0}=g_{i,0}+\max{f_{v,0},f_{v,1}}\f_{i,1}=g_{i,1}+f_{v,0}=\max{g_{i,1}+f_{v,0},-\infin}$$
若 $A$ 为 $n\times p$，$B$ 为 $p\times q$ 的矩阵，我们定义广义的矩阵乘法 $C=A\times B$，且 $C_{i,j}={\max\limits_{1\le k\le p} (A_{i,k}+B_{k,j})}$，由于 $\max$ 操作具有结合律，因此可以满足广义矩阵乘法的要求。
于是我们将转移写成矩阵的形式。那么便有：
$$\begin{bmatrix}f_{i,0}\f_{i,1}\end{bmatrix}=\begin{bmatrix}g_{i,0} & g_{i,0} \ g_{i,1} & -\infin\end{bmatrix}\begin{bmatrix}f_{v,0} \ f_{v,1} \end{bmatrix}$$
这种将转移式用广义矩阵乘法的 DP 形式，是**动态 DP（DDP）**的一般做法。
那该怎样用这种方法维护 $f$ 与 $g$？
首先在第二个 dfs 中，我们可以直接计算出 $f$ 和 $g$ 的结果，照着上面来一遍即可。
代码中的 $g$ 即为转移矩阵。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
void dfs2 (int x, int top) {
tp[x] = top;
id[x] = ++ tim; dfn[tim] = x; ed[top] = max (ed[top], tim);
f[x][0] = 0, f[x][1] = a[x];
g[x].M[0][0] = g[x].M[0][1] = 0; g[x].M[1][0] = a[x];
if (son[x]) {
dfs (son[x], top);
f[x][0] += max (f[ son[x] ][0], f[ son[x] ][1]);
f[x][1] += f[ son[x] ][0];
}
for (auto v : G[x]) {
if (id[v]) continue;
dfs (v, v);
f[x][0] += max (f[v][0], f[v][1]);
f[x][1] += f[v][0];
g[x].M[0][0] += max (f[v][0], f[v][1]);
g[x].M[0][1] = g[x].M[0][0];
g[x].M[1][0] += f[v][0];
}
}
|
修改，怎么做？
不妨设修改的点为 $u$，修改成的权值为 $w$，那么 $g_{u,1}$ 应该加上 $w-a_u$，并 $a_u\gets w$。
和正常树剖一样，从 $u$ 点往上跳，这里我们存了两个临时矩阵 $former$ 与 $latter$ 分别表示修改前的 $u$ 至其链顶 的$f$ 矩阵及修改后的 $f$ 矩阵。
将 $u$ 点跳到其所在链的链顶的父亲 $fa$，那么根据重链的定义，边 $(u,fa)$ 必定是一条轻边，也就是说 $u$ 及其子树 $S_u$ 会对 $g$ 做出贡献。
对于 $g_{fa,0}$，其余不变，仅修改 $S_u$ 这一子树的 $f$。因此我们仅需 加上变化值 即可。而状态转移式决定了我们的方式，但稍微思考，便知先取 $\max{g_{u,0},g_{u,1}}$ 再做差。
对于 $g_{fa,1}$，由于不取 $u$，故直接用 $latter$ 与 $former$ 做差即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void path_upd (int u, int w) {
g[u].M[1][0] += w - a[u];
a[u] = w;
Matrix former, latter;
while (u) {
former = T.query (1, id[ tp[u] ], ed[ tp[u] ]);
T.upd (1, id[u]);
latter = T.query (1, id[ tp[u] ], ed[ tp[u] ]);
int fa = fa[ tp[u] ];
g[fa].M[0][0] += max (latter.M[0][0], latter.M[1][0]) - max (former.M[0][0], former.M[1][0]);
g[fa].M[0][1] = g[fa].M[0][0];
g[fa].M[1][0] += latter.M[0][0] - former.M[0][0];
}
}
|
查询就比较显然了，答案就是根节点的最值。
1
2
|
auto ans = T.query (1, id[1], ed[1]);
printf ("%d\n", max (ans.M[0][0], ans.M[1][0]));
|
二、长链剖分