OI笔记 | 重链剖分笔记
重链剖分
模板题：洛谷 P3384
重链剖分可以把树分割成若干条链，且保证划分出的每条链上的节点 dfs 序连续，从而可以用维护序列的数据结构（如线段树）来维护树的路径上的信息。
我们定义 $hson(x)$ 为 $x$ 的重儿子，即 $x$ 的所有儿子中，子树大小最大的。
从一个节点到它的重子节点的边称为重边。若干条首尾衔接的重边构成重链。
只需要用两次简单的 dfs 就可以实现树剖。
第一次 dfs 中，我们需要求出每个节点的 重儿子 $hson(x)$、深度 $dep(x)$、以它为根的子树大小 $siz(x)$、父亲 $fa(x)$。
第二次 dfs 中，需要 优先 dfs 每个节点的重儿子，这可以让同一条重链上的点的 dfs 序连续。我们需要求出每个节点的 dfs序 $dfn(x)$、所在重链的深度最小的节点 $top(x)$。顺带着把点权赋值到序列上，即 $a_{dfn(x)}\gets v_x$。
到这一步树剖其实已经完成，已经可以用这些信息求 $\operatorname{LCA}(x,y)$ 了。实现就是将 $top$ 深度较大的节点往上跳到 $fa(top(x))$，直到两个节点在同一条重链上。代码如下：
int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] > dep[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
return dep[x] < dep[y] ? x : y;
}
考虑模板题中的信息维护，我们用一棵线段树来维护权值和。
先看操作 3 和 4，比较简单：
-
3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。 -
4 x表示求以 $x$ 为根节点的子树内所有节点值之和
由于子树内的 $dfn$ 也是连续的，所以对于子树内的修改与查询，我们只需要直接对区间 $[dfn(x),dfn(x)+siz(x)-1]$ 进行操作即可。
再看操作 1 和 2：
-
1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。 -
2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。
我们像 LCA 一样，每次让将 $top$ 深度较大的节点往上跳到 $fa(top(x))$，直到两个节点在同一条重链上。
每次跳的时候都 修改/查询 区间 $[dfn(top(x)),dfn(x)]$（$dep(top(x))>dep(top(y))$）。
最后在同一条重链上时再 修改/查询 区间 $[dfn(x), dfn(y)]$（$dep(x)<dep(y)$）。
注意这题每一步都要取模，我有一个地方没加取模然后调了半个小时。而且把数据下载下来调居然在 dfs 时就爆栈了，加了编译选项才正常。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
int n, m, rt, MOD, dfncnt;
int v[MAX_N], top[MAX_N], hson[MAX_N], dep[MAX_N], fa[MAX_N], siz[MAX_N], dfn[MAX_N];
int a[MAX_N], d[MAX_N << 2], b[MAX_N << 2];
vector<int> G[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void dfs1(int u, int pre) {
hson[u] = -1;
siz[u] = 1;
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v == pre) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
dfs1(v, u);
siz[u] += siz[v];
if(hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v;
}
}
void dfs2(int u, int tp) {
top[u] = tp;
dfn[u] = ++dfncnt;
a[dfncnt] = v[u];
if(hson[u] == -1) return;
dfs2(hson[u], tp);
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v != fa[u] && v != hson[u]) dfs2(v, v);
}
}
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return (s + ((t - s) >> 1));}
inline void pu(int p) {d[p] = (d[lc(p)] + d[rc(p)]) % MOD;}
inline void pd(int p, int s, int t) {
if(b[p]) {
int m = mid(s, t);
(d[lc(p)] += (m - s + 1) * b[p]) %= MOD;
(d[rc(p)] += (t - m) * b[p]) %= MOD;
(b[lc(p)] += b[p]) %= MOD;
(b[rc(p)] += b[p]) %= MOD;
b[p] = 0;
}
}
void build_tree(int s, int t, int p) {
if(s == t) {d[p] = a[s]; return;}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
pu(p);
}
void update(int s, int t, int p, int l, int r, int k) {
if(l <= s && t <= r) {
(d[p] += (t - s + 1) * k) %= MOD;
(b[p] += k) %= MOD;
return;
}
pd(p, s, t);
int m = mid(s, t);
if(l <= m) update(s, m, lc(p), l, r, k);
if(r > m) update(m + 1, t, rc(p), l, r, k);
pu(p);
}
int query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p];
pd(p, s, t);
int m = mid(s, t), ret = 0;
if(l <= m) (ret += query(s, m, lc(p), l, r)) %= MOD;
if(r > m) (ret += query(m + 1, t, rc(p), l, r)) %= MOD;
return ret;
}
void update_path(int x, int y, int k) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
update(1, n, 1, dfn[top[x]], dfn[x], k);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
update(1, n, 1, dfn[x], dfn[y], k);
}
int query_path(int x, int y) {
int ret = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
(ret += query(1, n, 1, dfn[top[x]], dfn[x])) %= MOD;
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
(ret += query(1, n, 1, dfn[x], dfn[y])) %= MOD;
return ret;
}
int main() {
n = read(), m = read(), rt = read(), MOD = read();
for(int i = 1; i <= n; i++) v[i] = read();
for(int i = 1; i <= n - 1; i++) {
int u = read(), v = read();
G[u].push_back(v), G[v].push_back(u);
}
dfs1(rt, 0);
dfs2(rt, rt);
build_tree(1, n, 1);
while(m--) {
int op = read();
if(op == 1) {
int x = read(), y = read(), k = read();
update_path(x, y, k);
}
else if(op == 2) {
int x = read(), y = read();
write(query_path(x, y));
putchar('\n');
}
else if(op == 3) {
int x = read(), k = read();
update(1, n, 1, dfn[x], dfn[x] + siz[x] - 1, k);
}
else {
int x = read();
write(query(1, n, 1, dfn[x], dfn[x] + siz[x] - 1));
putchar('\n');
}
}
return 0;
}
换根
模板题：LOJ 139
如果有换根的操作，会影响我们对子树的修改/查询。我们不可能换一次根树剖一次。事实上，换根后修改/查询以 $x$ 为根的子树，有三种情况：
-
当 $x=root$ 时，全局修改/查询。
-
当 $x$ 不在 $1$ 到 $root$ 的链上时，等价于修改/查询原来的子树。
-
当 $x$ 在 $1$ 到 $root$ 的链上时，等价于修改/查询 【$x$ 在 $root$ 方向的子树】 的补集。
想要判断出第 $3$ 种情况，首先要满足 $dep_{root} > dep_x$，其次我们可以倍增找到 $x$ 的第 $(dep_{root} - dep_x - 1)$ 倍祖先 $y$，如果 $y$ 的父亲恰是 $x$，则显然 $x$ 在 $1$ 到 $root$ 的链上。
第 $2$ 种情况对应的 dfs 序区间为 $[dfn_x, dfn_x + siz_x - 1]$。
第 $3$ 种情况，则对应的 dfs 序区间为 $[1, dfn_y - 1]\cup [dfn_y + siz_y, n]$。
例题 遥远的国度
给定一棵有 $n$ 个节点的树，初始每个点都有一个点权 $val_i$。
有 $m$ 次操作，每次：
-
把根节点更换成 $x$
-
将 $x$ 到 $y$ 路径上的所有点的点权都变为某个值
-
询问以 $x$ 为根的子树内的最小点权值
$1 \leq n\le 100000,1 \leq m \le 100000,0<val_i<2^{31}$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, INF = (1 << 30);
int val[MAX_N], rt, n, m;
int fa[MAX_N][25], siz[MAX_N], hson[MAX_N], dep[MAX_N];
int dfn[MAX_N], top[MAX_N], a[MAX_N], dfncnt;
int d[MAX_N << 2], b[MAX_N << 2];
vector<int> G[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void dfs1(int u, int pre) {
siz[u] = 1, hson[u] = -1;
for(int i = 1; i < 25; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
if(!fa[u][i]) break;
}
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v == pre) continue;
dep[v] = dep[u] + 1;
fa[v][0] = u;
dfs1(v, u);
siz[u] += siz[v];
if(hson[u] == -1 || siz[hson[u]] < siz[v]) hson[u] = v;
}
}
void dfs2(int u, int tp) {
dfn[u] = ++dfncnt;
a[dfncnt] = val[u];
top[u] = tp;
if(hson[u] == -1) return;
dfs2(hson[u], tp);
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v != fa[u][0] && v != hson[u]) dfs2(v, v);
}
}
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return s + ((t - s) >> 1);}
inline void pu(int p) {d[p] = min(d[lc(p)], d[rc(p)]);}
inline void pd(int p, int s, int t) {
if(b[p]) {
d[lc(p)] = d[rc(p)] = b[lc(p)] = b[rc(p)] = b[p];
b[p] = 0;
}
}
inline void build_tree(int s, int t, int p) {
if(s == t) {
d[p] = a[s];
return;
}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
pu(p);
}
inline void update(int s, int t, int p, int l, int r, int v) {
if(l <= s && t <= r) {
d[p] = b[p] = v;
return;
}
pd(p, s, t);
int m = mid(s, t);
if(l <= m) update(s, m, lc(p), l, r, v);
if(r > m) update(m + 1, t, rc(p), l, r, v);
pu(p);
}
inline int query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p];
pd(p, s, t);
int m = mid(s, t);
int ret = INF;
if(l <= m) ret = min(ret, query(s, m, lc(p), l, r));
if(r > m) ret = min(ret, query(m + 1, t, rc(p), l, r));
return ret;
}
inline void update_path(int x, int y, int v) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
update(1, n, 1, dfn[top[x]], dfn[x], v);
x = fa[top[x]][0];
}
if(dep[x] > dep[y]) swap(x, y);
update(1, n, 1, dfn[x], dfn[y], v);
}
inline int find(int x, int k) {
for(int i = 24; i >= 0; i--)
if(k >= (1 << i)) x = fa[x][i], k -= (1 << i);
return x;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n - 1; i++) {
int u = read(), v = read();
G[u].push_back(v), G[v].push_back(u);
}
for(int i = 1; i <= n; i++)
val[i] = read();
dfs1(1, 0), dfs2(1, 1);
rt = read();
build_tree(1, n, 1);
while(m--) {
int op = read();
if(op == 1) rt = read();
else if(op == 2) {
int x = read(), y = read(), v = read();
update_path(x, y, v);
}
else {
int x = read(), ans;
if(x == rt) ans = d[1];
else if(dep[rt] > dep[x]) {
int y = find(rt, dep[rt] - dep[x] - 1);
if(fa[y][0] == x) {
ans = query(1, n, 1, 1, dfn[y] - 1);
if(dfn[y] + siz[y] <= n) ans = min(ans, query(1, n, 1, dfn[y] + siz[y], n));
}
else ans = query(1, n, 1, dfn[x], dfn[x] + siz[x] - 1);
}
else ans = query(1, n, 1, dfn[x], dfn[x] + siz[x] - 1);
write(ans), putchar('\n');
}
}
return 0;
}
- 上一篇 OI笔记 | 2022.11 做题记录（二）
- 下一篇 OI笔记 | 数列分块笔记
♥