本文共 2774 字，大约阅读时间需要 9 分钟。
轻重链剖分是一种与传统链剖分相似的数据结构，它的核心区别在于对“重儿子”的定义进行了调整。传统链剖分中，重儿子的定义是“所在子树中的最大儿子”，而轻重链剖分中，重儿子则定义为“所在子树中的最深儿子”。这种改变使得轻重链剖分在处理与深度相关的问题时更加灵活，特别是在优化动态规划（DP）的过程中应用广泛。
轻重链剖分具有以下几个重要性质：
链长度和性质
所有链的长度总和为 (O(n)) 级别。这意味着在预处理和查询时，算法的时间复杂度主要取决于节点数量，而不会因为链的长度过长而变得不可控。祖先深度性质
任意一个点的 (k) 次祖先 (y) 所在的长链的长度至少为 (k)。这对于快速定位特定祖先节点非常有用，特别是在需要处理多个层次查询时。跳跃次数限制
任何一个点向上跳跃重链的次数不会超过 (\sqrt{n}) 次。这限制了算法在跳跃过程中的复杂度，确保在大数据量下依然能够高效运行。轻重链剖分在多个领域中有广泛应用，其中最为突出的两种应用是计算 (k) 次祖先和优化动态规划问题。
为了快速定位一个节点的 (k) 次祖先，轻重链剖分采取了以下预处理步骤：
算法的具体步骤如下：
这种方法的预处理复杂度为 (O(n \log n))，而单次查询仅需 (O(1)) 时间，极大提升了效率。
在动态规划优化方面，轻重链剖分的应用尤为突出。传统的DP优化方法通常面临复杂度瓶颈，而轻重链剖分通过链结构的特性，能够显著降低优化时间。
以一个典型问题为例，假设需要计算树上满足特定深度条件的节点对数。传统方法可能需要暴力遍历所有子树，复杂度为 (O(n^2))，而轻重链剖分可以将其优化为 (O(n))。
具体实现步骤如下：
这种方法充分利用了轻重链剖分的优势，将传统 (O(n^2)) 的复杂度降低至 (O(n))，极大提升了算法效率。
#includeconst int M = 100005;#define int long longint read() { int x = 0, f = 1; char c; while ((c = getchar()) < '0' || c > '9') { if (c == '-') f = -1; } while (c >= '0' && c <= '9') { x = (x < 3 ? x << 1 : x << 1) + (c - '0'); c = getchar(); } return x * f;}int n, tot, F[M], d[M], dep[M], son[M];int *f = (int *)malloc(M), *g = (int *)malloc(M), p[4 * M], *o = p, ans;struct edge { int v, next; edge(int v = 0, int N = 0) : v(V), next(N) {}} e[2 * M];void pre(int u, int fa) { d[u] = d[fa] + 1; for (int i = F[u]; i; i = e[i].next) { int v = e[i].v; if (v == fa) continue; pre(v, u); if (dep[v] > dep[son[u]]) son[u] = v; } dep[u] = dep[son[u]] + 1;}void dfs(int u, int fa) { if (son[u]) { f[son[u]] = f[u] + 1; g[son[u]] = g[u] - 1; dfs(son[u], u); } f[u][0] = 1; ans += g[u][0]; for (int i = F[u]; i; i = e[i].next) { int v = e[i].v; if (v == fa || v == son[u]) continue; f[v] = o; o += dep[v] * 2; g[v] = o; o += dep[v] * 2; dfs(v, u); for (int j = 0; j < 32; j++) { if (dep[v] & (1 << j)) { p[j] = v; } } }}
轻重链剖分通过对重儿子定义的调整，使其在深度相关问题中的应用更加灵活和高效。其预处理和查询的复杂度显著优于传统方法，广泛应用于 (k) 次祖先查询和动态规划优化等领域。如果需要更深入的理解和应用，可以通过实践和练习将这些理论转化为具体的算法实现。
转载地址：http://pjozz.baihongyu.com/