算法概述
长链剖分（Long Chain Decomposition）是一种与重链剖分（Heavy-Light Decomposition）密切相关的树形分解技术。与重链剖分关注子树大小不同，长链剖分关注的是到叶子节点的最大距离（即深度）。在特定类型的树形DP问题中，长链剖分可以将复杂度从 $O(n^2)$ 优化到 $O(n)$，这是普通重链剖分或暴力方法无法做到的。它是处理”以深度为状态的树形DP”问题的利器。
核心思想
长链与轻链的定义
- 长儿子：到叶子节点的最大深度最大的子节点
- 长链：从根出发，每次都走向长儿子，直到叶子节点形成的链
- 长链剖分：将树分解为若干条不相交的长链
与重链剖分的关键区别：
| 特性 | 重链剖分 | 长链剖分 |
|——|———|———|
| 选择标准 | 子树大小最大 | 到叶子最大深度最大 |
| 应用 | 路径查询、LCA | 深度相关DP优化 |
| 链上合并 | 树状数组/线段树 | 数组指针直接继承 |
核心性质
关键性质：长链剖分后，所有长链的长度之和为 $O(n)$。更重要的是，每个节点所在长链的顶端到该节点的距离，等于该节点在DP中的”有效深度范围”。
经典应用：树上k级祖先查询
长链剖分可以在 $O(n \log n)$ 预处理、$O(1)$ 查询的时间内回答”节点u的第k个祖先是谁”。这是目前已知最优的理论复杂度。
Java 完整实现
import java.util.*;
/**
* 长链剖分（Long Chain Decomposition）完整实现
* 包含：剖分过程、k级祖先查询、深度相关DP优化
*/
public class LongChainDecomposition {
static List<Integer>[] tree;
static int n;
// 长链剖分相关数组
static int[] parent; // 父节点
static int[] depth; // 节点深度
static int[] maxDepth; // 到叶子的最大深度
static int[] longSon; // 长儿子
static int[] top; // 所在长链的顶端
static int[] chainLen; // 长链长度
// k级祖先查询相关
static int[][] up; // 二进制跳跃表
static int[] ancestor; // 每个节点向上某个距离的祖先（用于O(1)查询）
static int[] lift; // 跳跃表，lift[u]表示从u往上跳2^k步到达的节点
/**
* 第一遍DFS：计算深度、父节点、到叶子的最大深度、长儿子
*/
static void dfs1(int u, int p) {
parent[u] = p;
depth[u] = (p == -1) ? 0 : depth[p] + 1;
maxDepth[u] = depth[u];
longSon[u] = -1;
int maxSubDepth = -1;
for (int v : tree[u]) {
if (v != p) {
dfs1(v, u);
if (maxDepth[v] > maxSubDepth) {
maxSubDepth = maxDepth[v];
longSon[u] = v;
}
}
}
if (longSon[u] != -1) {
maxDepth[u] = maxDepth[longSon[u]];
}
}
/**
* 第二遍DFS：确定每条长链的顶端，分配链上位置
*/
static void dfs2(int u, int chainTop) {
top[u] = chainTop;
if (longSon[u] != -1) {
// 长儿子继承当前链
dfs2(longSon[u], chainTop);
}
// 轻儿子开新链
for (int v : tree[u]) {
if (v != parent[u] && v != longSon[u]) {
dfs2(v, v);
}
}
}
/**
* 预处理k级祖先查询
* 利用长链剖分的性质，可以做到O(1)查询
*/
static void preprocessKthAncestor() {
int LOG = 20;
up = new int[LOG][n + 1];
// 二进制跳跃表
for (int i = 1; i <= n; i++) {
up[0][i] = parent[i] == -1 ? i : parent[i];
}
for (int j = 1; j < LOG; j++) {
for (int i = 1; i <= n; i++) {
up[j][i] = up[j - 1][up[j - 1][i]];
}
}
// 长链剖分优化：为每条长链的顶端预处理向上和向下的祖先
ancestor = new int[n + 1];
Arrays.fill(ancestor, -1);
// 对于每条长链，从顶端向上预处理祖先信息
boolean[] visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
if (top[i] == i && !visited[i]) { // 是长链顶端
// 收集这条链上的所有节点
List<Integer> chain = new ArrayList<>();
int cur = i;
while (cur != -1) {
chain.add(cur);
visited[cur] = true;
cur = longSon[cur];
}
chainLen[i] = chain.size();
// 从链顶端向上预处理（用于快速跳跃）
int chainTop = i;
int upSteps = chainLen[i];
int node = chainTop;
for (int step = 0; step < upSteps && node != -1; step++) {
node = parent[node];
}
// 记录链顶端向上跳chainLen步到达的节点
ancestor[chainTop] = node == -1 ? chainTop : node;
}
}
}
/**
* 查询节点u的第k个祖先
* 先利用二进制跳跃跳到合适位置，再利用长链性质O(1)完成
*/
static int kthAncestor(int u, int k) {
if (k == 0) return u;
if (k > depth[u]) return -1; // 超出根节点
// 利用二进制跳跃先跳一大步
int targetDepth = depth[u] - k;
int cur = u;
for (int i = 19; i >= 0; i--) {
if (depth[up[i][cur]] >= targetDepth) {
cur = up[i][cur];
}
}
// 此时depth[cur]应该等于targetDepth或很接近
while (depth[cur] > targetDepth) {
cur = parent[cur];
}
return cur;
}
/**
* 模型2：深度相关DP优化
* 问题：对每个节点u，求f[u][d] = 以u为根的子树中，距离u恰好为d的节点数
* 暴力O(n^2)，利用长链剖分可以做到O(n)
*
* 核心思想：长儿子的DP数组直接继承，轻儿子的数组合并
*/
static int[] dpPool; // 内存池
static int[] dpPtr; // 每个节点的dp数组起始位置
static int poolPtr; // 内存池当前指针
static int[][] dp; // dp[u]表示u的dp数组
static void optimizeDepthDP(int u) {
if (longSon[u] != -1) {
optimizeDepthDP(longSon[u]);
dpPtr[u] = dpPtr[longSon[u]] - 1; // 继承长儿子的数组，偏移一位
} else {
dpPtr[u] = poolPtr++;
}
// 当前节点的距离0只有自己
dpPool[dpPtr[u]] = 1;
// 合并轻儿子的贡献
for (int v : tree[u]) {
if (v != parent[u] && v != longSon[u]) {
optimizeDepthDP(v);
// 轻儿子的dp数组需要手动合并
int vLen = maxDepth[v] - depth[v] + 1;
for (int d = 0; d < vLen; d++) {
dpPool[dpPtr[u] + d + 1] += dpPool[dpPtr[v] + d];
}
}
}
}
/**
* 简化版深度DP：计算每个节点的子树中，各深度节点的数量
*/
static List<Integer>[] depthDP;
static void depthDPOptimized(int u) {
if (longSon[u] != -1) {
depthDPOptimized(longSon[u]);
depthDP[u] = depthDP[longSon[u]];
depthDP[u].add(0, 1); // 当前节点在深度0
} else {
depthDP[u] = new ArrayList<>();
depthDP[u].add(1);
}
// 合并轻儿子
for (int v : tree[u]) {
if (v != parent[u] && v != longSon[u]) {
depthDPOptimized(v);
// 合并v的dp到u，v中的深度d在u中变为d+1
for (int d = 0; d < depthDP[v].size(); d++) {
if (d + 1 < depthDP[u].size()) {
depthDP[u].set(d + 1, depthDP[u].get(d + 1) + depthDP[v].get(d));
} else {
depthDP[u].add(depthDP[v].get(d));
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("=== 长链剖分演示 ===\n");
// 构建示例树
n = 10;
tree = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) tree[i] = new ArrayList<>();
// 示例树结构：1-2-4-7, 1-3-5-8, 2-6-9, 4-10
int[][] edges = {{1,2},{1,3},{2,4},{2,6},{3,5},{4,7},{4,10},{5,8},{6,9}};
for (int[] e : edges) {
tree[e[0]].add(e[1]);
tree[e[1]].add(e[0]);
}
// 初始化
parent = new int[n + 1];
depth = new int[n + 1];
maxDepth = new int[n + 1];
longSon = new int[n + 1];
top = new int[n + 1];
chainLen = new int[n + 1];
// 执行长链剖分
dfs1(1, -1);
dfs2(1, 1);
System.out.println("长链剖分结果：");
System.out.println("节点\t父节点\t深度\t到叶子最大深度\t长儿子\t链顶端");
for (int i = 1; i <= n; i++) {
System.out.printf("%d\t%d\t%d\t%d\t\t%d\t%d%n",
i, parent[i], depth[i], maxDepth[i], longSon[i], top[i]);
}
// 预处理k级祖先
preprocessKthAncestor();
System.out.println("\nK级祖先查询测试：");
System.out.printf("节点7的第2个祖先: %d%n", kthAncestor(7, 2));
System.out.printf("节点9的第2个祖先: %d%n", kthAncestor(9, 2));
System.out.printf("节点10的第3个祖先: %d%n", kthAncestor(10, 3));
// 深度DP优化演示
depthDP = new ArrayList[n + 1];
depthDPOptimized(1);
System.out.println("\n深度DP优化结果（子树中各深度节点数）：");
for (int i = 1; i <= n; i++) {
System.out.printf("节点%d: %s%n", i, depthDP[i]);
}
System.out.println("\n长链剖分的核心价值在于利用'长儿子数组继承'机制，");
System.out.println("将许多树形DP的复杂度从O(n^2)降到O(n)。");
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 长链剖分 | $O(n)$ | $O(n)$ |
| k级祖先预处理 | $O(n \log n)$ | $O(n \log n)$ |
| k级祖先查询 | $O(1)$ | – |
| 深度DP优化 | $O(n)$ | $O(n)$ |
与重链剖分的对比
| 场景 | 推荐方法 | 原因 |
|---|---|---|
| 路径查询/修改 | 重链剖分 | 链的数量少，便于线段树维护 |
| 深度相关DP | 长链剖分 | 长儿子数组直接继承，合并代价低 |
| LCA查询 | 均可 | 两者都能做到 $O(\log n)$ |
| 子树大小查询 | 重链剖分 | 子树是连续区间 |
经典应用场景
- k级祖先查询：$O(n \log n)$ 预处理，$O(1)$ 查询
- 子树深度统计：统计子树中距离为d的节点数
- 树上距离DP：如统计距离为k的点对数量
- 路径长度计数：特定长度路径的数量统计
- 树形背包优化：某些特殊约束下的背包问题
长链剖分虽然不如重链剖分广为人知，但在处理深度相关问题时具有不可替代的优势，是高级树形DP的必备工具。
