【8】树链剖分 学习笔记

· · 算法·理论

引入

树链剖分，顾名思义，就是将一棵树剖成一条条链。这种算法可以帮助我们快速解决一类和树上路径有关的的问题。

P3384 【模板】重链剖分 / 树链剖分

给定一棵 n 个点的树，需要支持 q 次询问，分为如下几种：

--- ## 算法流程 既然知道了需要剖，那么怎么剖，以及剖好之后如何解决问题？下面我们详细说说。 ### 怎么剖 首先看怎么剖。树剖有两种，一种是重链剖分，一种是长链剖分，后者用的比较少，这里我们讲前面这种。 对于树上每个点，我们记录其**重儿子**为其所有儿子中子树大小最大的那一个，**重边**为其连向重儿子的边。其余的则反过来，称为轻儿子和轻边。例如下图中的树： ![](https://cdn.luogu.com.cn/upload/image_hosting/67zlzcxk.png) - 每个点旁边用蓝笔写出了其重儿子； - 叉表示该点是叶子，没有儿子。 - 像 $5$ 这种有多个最大子树的，可以任选一个作为重儿子。 - 绿色的边就是重边。 像这种多个重边连起来的（如 $1 \to 2$，$2 \to 5$，$5 \to 7$）（当然单个重边也是可以的）一条链就叫做**重链**，这条链最上面一个点（此处为 $1$）就叫做该链的**链头**。对于一棵树上的任意一个点，我们有性质： - 一个点最多向上跳 $O(\log n)$ 条重链就会跳到根。 理解一下这个性质。 - 首先，啥叫“跳”啊？ - 跳就是，每一次跳到**当前所在重链**的**链头的父亲**。 - 如果一个点到其父亲的边不是重边呢？ - 这里可以把这个点看作一个包含 $0$ 个重边的重链，跳到其父亲即可。 - 为啥只会跳 $O(\log n)$ 次？ - 感性理解一下，每次跳过一条重链，为了满足**重链的性质**（也就是重儿子的性质，其子树比其它子树都要大），可能的整个树的大小就要翻倍。所以这里只会跳 $O(\log n)$ 次。 这些信息都可以用一次 DFS 求出。这样就完成了我们的剖分过程，下面我们来看看这个有什么用。 ### 如何用 来回到例题，看看树剖咋用。 首先我们基本就不会啥树上的数据结构，考虑把这棵树拍平到序列上，这样我们的操作就比较好进行了。 咋拍呢，我们也没学过啥别的啊，就直接用 DFS 序吧。 但是这样我们重链的优秀性质就没了——那怎么行！我们想到一个折中方案：DFS 的时候，如果该点不是叶子，那么先遍历重儿子。这样，一条重链上的点的 DFS 序就是**连续的**了。 看起来问题差不多解决了，因为子树修和子树和都可以用 DFS 序拍成区间加和区间求和。链也可以，因为有性质，我们直接一直向上跳就可以了。 但是我们怎么知道跳到哪里是 LCA 呢？如果 LCA 在一个重链中间怎么办？这里有一个解决办法：我们每次选**链头深度大**的那边跳上去，直到 $x$ 和 $y$ 在同一条重链上。因为 LCA 这个点至少有一个轻儿子（否则，$x$ 和 $y$ 就已经在一条重链了，这里可以自行思考），所以总有一个点会正好跳到 LCA 上面。当跳到一条重链上面的时候，此时一个点是 LCA，另一个点一定是其后代，此时这两个点之间的链也一定在原来的 $x \to y$ 路径上，而且 DFS 序也是连续的。 这就意味着，我们可以将一条链拆成序列上的 $O(\log n)$ 个连续区间，然后就可以直接线段树啦~ 线段树就是区间加，区间求和就可以了。 分析一下复杂度： - 空间上，没啥特别的，就是 $O(n)$。 - 时间上，我们在跳重链的时候要跳 $O(\log n)$ 次，每次要花 $O(\log n)$ 的时间更新，所以总时间复杂度是 $O(n \log^2 n)$。 代码比较好写。 :::info[Code]{open} ```cpp #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5; int a[N], dfnid; vector<int> e[N]; int siz[N], son[N], dep[N], fa[N], dfn[N], top[N], d[N]; struct segtree { int tree[4 * N], tag[4 * N]; void pushup(int x) { tree[x] = tree[x*2] + tree[x*2+1]; } void pushdown(int x, int l, int r) { int mid = (l + r) >> 1; tree[x*2] += (mid-l+1) * tag[x]; tree[x*2+1] += (r-mid) * tag[x]; tag[x*2] += tag[x]; tag[x*2+1] += tag[x]; tag[x] = 0; } void build(int x, int l, int r) { if(l == r) return tree[x] = a[d[l]], tag[x] = 0, void(); int mid = (l + r) >> 1; build(x*2, l, mid); build(x*2+1, mid+1, r); pushup(x); } void update(int x, int l, int r, int L, int R, int d) { if(R < l || L > r) return ; if(L <= l && r <= R) return tree[x] += (r-l+1) * d, tag[x] += d, void(); pushdown(x, l, r); int mid = (l + r) >> 1; update(x*2, l, mid, L, R, d); update(x*2+1, mid+1, r, L, R, d); pushup(x); } int query(int x, int l, int r, int L, int R) { if(R < l || L > r) return 0; if(L <= l && r <= R) return tree[x]; pushdown(x, l, r); int mid = (l + r) >> 1; return query(x*2, l, mid, L, R) + query(x*2+1, mid+1, r, L, R); } } tr; void dfs1(int now, int f) { fa[now] = f; dep[now] = dep[f] + 1; siz[now] = 1; int mxsz = 0, mxid = 0; for(auto x : e[now]) { if(x == f) continue; dfs1(x, now); siz[now] += siz[x]; if(siz[x] > mxsz) mxsz = siz[x], mxid = x; } son[now] = mxid; } void dfs2(int now, int f, int rt) { dfn[now] = ++dfnid; top[now] = rt; if(son[now]) dfs2(son[now], now, rt); for(auto x : e[now]) { if(x == f || x == son[now]) continue; dfs2(x, now, x); } } signed main() { int n, m, r, p; cin >> n >> m >> r >> p; for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 1, u, v;i < n;i++) cin >> u >> v, e[u].push_back(v), e[v].push_back(u); dfs1(r, 0); dfs2(r, 0, r); for(int i = 1;i <= n;i++) d[dfn[i]] = i; tr.build(1, 1, n); while(m--) { int opt, x, y, z; cin >> opt >> x; if(opt == 1) { cin >> y >> z; while(top[x] != top[y]) { if(dep[top[x]] > dep[top[y]]) swap(x, y); tr.update(1, 1, n, dfn[top[y]], dfn[y], z); y = fa[top[y]]; } if(dep[x] > dep[y]) swap(x, y); tr.update(1, 1, n, dfn[x], dfn[y], z); } else if(opt == 2) { cin >> y; int sum = 0; while(top[x] != top[y]) { if(dep[top[x]] > dep[top[y]]) swap(x, y); sum += tr.query(1, 1, n, dfn[top[y]], dfn[y]); y = fa[top[y]]; } if(dep[x] > dep[y]) swap(x, y); sum += tr.query(1, 1, n, dfn[x], dfn[y]); cout << sum % p << endl; } else if(opt == 3) { cin >> z; tr.update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, z); } else { cout << tr.query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) % p << endl; } } return 0; } ``` ::: ## 练习题 1 - [P3178 [HAOI2015] 树上操作](https://www.luogu.com.cn/problem/P3178) - [P3833 [SHOI2012] 魔法树](https://www.luogu.com.cn/problem/P3833) - [P2590 [ZJOI2008] 树的统计](https://www.luogu.com.cn/problem/P2590) - [P2146 [NOI2015] 软件包管理器](https://www.luogu.com.cn/problem/P2146) 这些题目只需稍微转换一下题意，或改一下线段树即可。 ## 边权转点权 有些题需要我们维护的是边权，而不是点权，怎么办呢？ --- ### [P4315 月下“毛景树”](https://www.luogu.com.cn/problem/P4315) 给定一棵树，进行如下几种操作： - `Change k w`：将第 $k$ 条树枝上毛毛果的个数改变为 $w$ 个。 - `Cover u v w`：将节点 $u$ 与节点 $v$ 之间的树枝上毛毛果的个数都改变为 $w$ 个。 - `Add u v w`：将节点 $u$ 与节点 $v$ 之间的树枝上毛毛果的个数都增加 $w$ 个。 - `Max u v`：询问节点 $u$ 与节点 $v$ 之间树枝上毛毛果个数最多有多少个。 $n,q \le 10^5$。 ---- 边权直接处理起来挺麻烦的，能不能想个办法转成点权呢？当然可以！我们让每个边里深度较大的那个点作为“代表”，把边权换成这个点的点权就好了。修改和查询的时候，需要注意不要把 LCA 也改了，因为 LCA 存的是它上面那条边，所以最后一次更新的时候从 LCA 的儿子开始即可。 ---- ## 练习题 2 - [P1505 [国家集训队] 旅游](https://www.luogu.com.cn/problem/P1505) - [P2680 [NOIP 2015 提高组] 运输计划](https://www.luogu.com.cn/problem/P2680) ## 总结 & 后记 树链剖分是一种很常用（？的算法，可以和很多其他数据结构结合，灵活使用。 这篇主要是基础内容，后面如果需要可能（？会更进阶 qaq。 --- 码字不易，能否给个赞 /wq >< 若对文章有任何问题和建议可以与作者私信交流。