长链剖分 学习笔记

长链剖分常用于优化一类特殊的动规，它可以在满足某些要求时，将 $\mathcal O(n)$ 的转移复杂度均摊为 $\mathcal O(1)$。此外，长链剖分还有一些优秀的性质，目前长链剖分在信息学竞赛中应用很广泛。

定义

众所周知，树链剖分通常指的是「重链剖分」，即只保留树上每个点与其子树大小最大的儿子之间的边，会形成一条条重链。重链剖分有许多优秀的性质。

「长链剖分」也是一种树链剖分，与「重链剖分」不同的是，「长链剖分」保留的是树上每个点与其子树深度最大的儿子之间的边。

与「重链剖分」一样，「长链剖分」也有许多优秀的性质。

性质

1. 树上所有长链的长度和是 $\mathcal O(n)$ 的。
2. 任意一个点的 $k$ 级祖先所在的长链长度一定 $\ge k$。

这两条性质的正确性都很显然，在此不证。

【例题】P5903 【模板】树上 k 级祖先

长链剖分的经典应用。

显然这个问题有 $\mathcal O(n \log n) - \mathcal O(\log n)$ 的树上倍增做法，然而还不够优秀。

首先我们进行预处理：

1. 对树进行长链剖分，记录每个点所在链的顶点和深度，$\mathcal O(n)$。
2. 树上倍增求出每个点的 $2^n$ 级祖先，$\mathcal O(n \log n)$。
3. 对于每条链，如果其长度为 $len$，那么在顶点处记录顶点向上的 $len$ 个祖先和向下的 $len$ 个链上的儿子，$\mathcal O(n)$。
4. 对 $i \in [1, n]$ 求出在二进制下的最高位 $h_i$，$\mathcal O(n)$。

对于每次询问 $x$ 的 $k$ 级祖先：

1. 利用倍增数组先将 $x$ 跳到 $x$ 的 $2^{h_k}$ 级祖先，设剩下还有 $k^{\prime}$ 级，显然 $k^{\prime} < 2^{h_k}$，因此此时 $x$ 所在的长链长度一定 $\ge 2^{h_k} > k^{\prime}$。
2. 由于长链长度 $> k^{\prime}$，因此可以先将 $x$ 跳到 $x$ 所在链的顶点，若之后剩下的级数为正，则利用向上的数组求出答案，否则利用向下的数组求出答案。

这样时间复杂度为 $\mathcal O(n \log n) - \mathcal O(1)$ 的。

const int N = 5e5 + 7;
int n, q, rt, g[N], d[N], f[N][21], son[N], dep[N], top[N], ans;
vi e[N], u[N], v[N];
ui s;
ll Ans;

inline ui get(ui x) {
	return x ^= x << 13, x ^= x >> 17, x ^= x << 5, s = x; 
}

void dfs(int x) {
	dep[x] = d[x] = d[f[x][0]] + 1;
	for (auto y : e[x]) {
		f[y][0] = x;
		for (int i = 0; f[y][i]; i++) f[y][i+1] = f[f[y][i]][i];
		dfs(y);
		if (dep[y] > dep[x]) dep[x] = dep[y], son[x] = y;
	}
}

void dfs(int x, int p) {
	top[x] = p;
	if (x == p) {
		for (int i = 0, o = x; i <= dep[x] - d[x]; i++)
			u[x].pb(o), o = f[o][0];
		for (int i = 0, o = x; i <= dep[x] - d[x]; i++)
			v[x].pb(o), o = son[o];
	}
	if (son[x]) dfs(son[x], p);
	for (auto y : e[x]) if (y != son[x]) dfs(y, y);
}

inline int ask(int x, int k) {
	if (!k) return x;
	x = f[x][g[k]], k -= 1 << g[k], k -= d[x] - d[top[x]], x = top[x];
	return k >= 0 ? u[x][k] : v[x][-k];
}

int main() {
	rd(n), rd(q), rd(s), g[0] = -1;
	for (int i = 1; i <= n; i++)
		rd(f[i][0]), e[f[i][0]].pb(i), g[i] = g[i>>1] + 1;
	rt = e[0][0], dfs(rt), dfs(rt, rt);
	for (int i = 1, x, k; i <= q; i++) {
		x = (get(s) ^ ans) % n + 1;
		k = (get(s) ^ ans) % d[x];
		Ans ^= 1ll * i * (ans = ask(x, k));
	}
	print(Ans);
	return 0;
}

应用

类似 dsu on tree，当前结点直接继承重儿子的信息，轻儿子信息暴力统计。

但由于是长链剖分，所以只能维护以深度为下标的信息。

考虑时间复杂度。

对于每个点，如果它是重儿子，由于是直接继承，因此对复杂度的贡献为 $\mathcal O(1)$，那么所有重儿子对复杂度的总贡献为 $\mathcal O(n)$。

如果它是轻儿子，那么需要转移给父亲的信息大小为其所在重链的长度，因此对复杂度的总贡献也为 $\mathcal O(n)$。

那么总时间复杂度为非常优秀的 $\mathcal O(n)$。

【例题】P5904 [POI2014]HOT-Hotels 加强版

先考虑简单版的 $n \le 5 \times 10^3$ 怎么做。

设 $f_{i,j}$ 为满足 $x$ 在 $i$ 的子树中且 $d(x, i) = j$ 的 $x$ 的个数，$g_{i,j}$ 为满足 $x,y$ 在 $i$ 的子树中且 $d(\operatorname{lca}(x, y), x) = d(\operatorname{lca}(x, y), y) = d(\operatorname{lca}(x, y), i) + j$ 的无序数对 $(x,y)$ 的个数。

有转移：

$$ans \leftarrow g_{i, 0}$$

$$ans \leftarrow \sum_{x,y \in \operatorname{son}(i), x \ne y} f_{x,j-1} \times g_{y,j+1}$$

$$g_{i,j} \leftarrow \sum_{x,y \in \operatorname{son}(i), x \ne y} f_{x,j-1} \times f_{y,j-1}$$

$$g_{i,j} \leftarrow \sum_{x \in \operatorname{son}(i)} g_{x, j+1}$$

$$f_{i,j} \leftarrow \sum_{x \in \operatorname{son}(i)} f_{x, j-1}$$

显然这可以利用前缀和，或者说是所有儿子「向 $i$ 合并」，做到 $\mathcal O(n)$ 转移，总时间复杂度 $\mathcal O(n^2)$。

注意到这里的信息都是以深度为下标的，那么可以利用长链剖分将复杂度降为均摊 $\mathcal O(1)$，总时间复杂度即可降为 $\mathcal O(n)$。

在「直接继承重儿子的信息」时，需要用指针维护，具体见代码。

const int N = 1e5 + 7;
int n, d[N], dep[N], son[N];
vi e[N];
ll *f[N], *g[N], p[N<<2], *o = p, ans;

void dfs(int x, int fa) {
	d[x] = d[fa] + 1;
	for (auto y : e[x])
		if (y != fa) {
			dfs(y, x);
			if (dep[y] > dep[son[x]]) son[x] = y;
		}
	dep[x] = dep[son[x]] + 1;
}

void dp(int x, int fa) {
	if (son[x])
		f[son[x]] = f[x] + 1, g[son[x]] = g[x] - 1, dp(son[x], x);
	f[x][0] = 1, ans += g[x][0];
	for (auto y : e[x])
		if (y != fa && y != son[x]) {
			f[y] = o, o += dep[y] << 1, g[y] = o, o += dep[y] << 1;
			dp(y, x);
			for (int i = 0; i < dep[y]; i++) {
				if (i) ans += f[x][i-1] * g[y][i];
				ans += g[x][i+1] * f[y][i];
			}
			for (int i = 0; i < dep[y]; i++) {
				g[x][i+1] += f[x][i+1] * f[y][i];
				if (i) g[x][i-1] += g[y][i];
				f[x][i+1] += f[y][i];
			}
		}
}

int main() {
	rd(n);
	for (int i = 1, x, y; i < n; i++)
		rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	dfs(1, 0), f[1] = o, o += dep[1] << 1, g[1] = o, o += dep[1] << 1;
	dp(1, 0), print(ans);
	return 0;
}

【练习】CF526G Spiders Evil Plan

参考资料

• 后缀自动机·张 长链剖分之 $\mathcal O(n\log n)-\mathcal O(1)$ 求 $k$ 级祖先
• Bill Yang 长链剖分学习总结