「学习笔记」长链剖分

简介

长链剖分是一种树链剖分，与重链剖分不同的是，每个点的关键儿子是它向下高度最大的儿子。

长链剖分有许多优美的性质。例如，某个点的 $k$ 级祖先所在链的边数一定不小于 $k$；任意两点之间只会跨过 $\sqrt n$ 条链。另外，长链剖分还可以在线性的时间内解决状态规模为子树高度的许多 dp。

k 级祖先

「Vijos 巴蜀中学」lxhgww 的奇思妙想

题目描述

给定一棵 $n$ 个点的树，$q$ 次询问点 $x$ 的 $k$ 级祖先。

强制在线，复杂度要求 $O(n \log n) - O(1)$。

思路分析

考虑利用简介中提到的一个性质：“某个点的 $k$ 级祖先所在链的长度一定不小于 $k$”。我们先用倍增预处理出每个点向上跳 $2^t$ 步会到达哪个点。考虑 $k$ 在二进制下的最高位 $b$，记 $x$ 的 $2^b$ 级祖先为 $y$，然后我们只要求 $y$ 的 $k - 2^b$ 级祖先。首先有 $y$ 所在链的长度不小于 $2^b$，然后发现 $k - 2^b < 2^b$，所以 $y$ 所在链的长度一定超过 $k - 2^b$。我们只需要处理出每个链顶向上跳不超过链长步会到达哪些点，存进 std::vector 中即可 $O(1)$ 查询 $y$ 的 $k - 2^b$ 级祖先。时间复杂度 $O(n \log n) - O(1)$。

代码实现

这题 RE on #6, 7, 8 实在调不出来了，代码仅供参考。

#include <bits/stdc++.h>

贪心

「BZOJ 3252」攻略

题目描述

给定点带权的点数为 $n$ 的树，要选出 $k$ 条包含 $1$ 的祖先后代链，使得它们并的点权和最大。

$n \le 2 \times 10^5, 1 \le a_i < 2^{31}$。

思路分析

考虑带权的长链剖分，剖出的链取前 $k$ 条加起来即可。时间复杂度 $O(n \log n)$。

代码实现

#include <bits/stdc++.h>

模版题

「CF 1009F」Dominant Indices

题目描述

记 $f(u, i)$ 为 $u$ 往下走 $i$ 步到达的点数，给定 $n$ 个点的树，对于每个点求出序列 $[f(u, 0), f(u, 1), \cdots]$ 中的最大值的最小下标。

数据范围：$n \le 10^6$。

思路分析

考虑长链剖分求 $f$，对于一个点，先继承特殊儿子的答案，然后对于其他儿子暴力更新即可。时间复杂度 $O(n)$。

代码实现

用 std::vector 实现，代码更短哦！

#include <bits/stdc++.h>

重建计划

「WC 2010」重建计划

题目描述

给定边带权的 $n$ 个点的树，选出一条长度在 $[L, U]$ 内的链，使得边权的平均值最小。

数据范围：$n \le 10^5$。

思路分析

首先可以想到二分答案，问题变成链的最大权值和是否超过 $0$。考虑长链剖分，设 $f(u, i)$ 表示 $u$ 的子树内以 $u$ 为端点的权值最大的长度为 $i$ 的路径长度。我们考虑使用线段树维护 $f$，从特殊儿子继承时只需要区间加，从其他儿子先更新答案（线段树区间最大值），后更新 $f$（暴力）即可。时间复杂度 $O(n \log^2 n)$。

代码实现

注意这个题不能用 std::vector，而是要使用内存分配的技巧。对于每一条链，我们改变 dfs 的顺序，使得每条链的 dfs 序连续。这样开一个全局的线段树，一条链上的一段就可以对应线段树的一个区间了。推荐简单题使用 std::vector，难题使用内存分配的方法。（因为难题用 std::vector 会写自闭的，详见 HOT Hotels）

#include <bits/stdc++.h>

HOT Hotels

「POJ 2014」HOT Hotels

题目描述

给定 $n$ 个点的树，求有多少点的三元组满足它们两两之间距离相等。

数据范围：$n \le 10^5$。

思路分析

发现三元组肯定有一个中心到三个点距离相等。记 $f(u, i)$ 表示 $u$ 子树内和它距离为 $i$ 的点数，$g(u, i)$ 表示 $u$ 子树内有多少点对满足它们到 LCA 的距离都为 $t$ 且 LCA 到 $u$ 的距离为 $t - i$（也就是说在上面加上长度为 $i$ 的链后可以形成方案）。那么转移方程如下：

for(int i = 0;i <= n;i ++) ans += g[x][i] * (i == 0 ? 0 : f[to][i-1]) + g[to][i+1] * f[x][i];

（转自 Treaker 的博客）

注意 $f(u, 0)$ 的初值为 $1$，dfs 完 $u$ 时还要让 $\text{ans} \leftarrow \text{ans} + g(u, 0)$。

那么使用长链剖分优化即可。时间复杂度 $O(n)$。

代码实现

用 std::vector 写的，由于 $g$ 数组转移的特殊，下标的变化很玄学，细节比较多。使用分配内存的方法就可以减少细节量。

// f[x][i] = p[x][f[x].size() - i - 1]