树上问题：树上倍增

Vector_Li · 2024-11-19 19:27:46 · 算法·理论

「Codeforces」Minimum spanning tree for each edge

使用 Kruskal 算法求出任意一颗 MST，设权值和为 t。

对于 (u, v)，权值为 w，求出 MST 上 u 到 v 的边集的最大权值，设其为 x，则答案为 t - x + w。

如何求解树上 2 点之间的边集的最大权值，涉及 2 个技巧：

边权转点权，我们在节点 u 处存储连接 u 和 p[u] 的边的信息（如果存在 p[u]）。
树上倍增，设 p[i][u] 表示 u 的 2^i - 1 级祖先节点，p[0][u] 就是 u 的父亲节点；设 f[i][u] 表示 p[i][u] 到 u 的路径上的所有点权值最大值。

具体细节请参考代码实现：CODE。

树上差分。设我们要对 u 到 v 的路径上的所有节点权值加 x，且 v 是 u 的祖先。我们设差分数组 d[i]。则 d[u] = d[u] + x，d[p[v]] = d[p[v]] - x。

如果 u 和 v 不构成祖先关系，设 w = LCA(u, v)，分段处理即可，注意对 w 分类讨论。

统计答案树上前缀和即可，类似求解子树大小的过程。

k = 1 的情况就是「LNOI 2014」LCA，我们先从这个题目开始。

设 d 表示深度，d[0] = 1。

\sum_{i = l}^r d(\operatorname{LCA}(i, u))

观察式子，我们首先可以使用前缀和将 [l, r] 共 2 个变量减少到 1 个变量。但是 d[LCA(i, x)] 的求解仍然困难，因为有 LCA 的存在。

大脑不妨抛开一系列求解 LCA 的算法（HLD，树上倍增），思考，LCA 最简单的求解方法是什么？

如果我们要求 LCA(u, v)，我们可以将 v 到根路径上的所有节点打上标记，此时 u 的第一个有标记的祖先就是 LCA(u, v)。

诶？LCA(u, v) 求出来了，那 d[LCA(u, v)] 不就是 u 到根路径上所有节点的标记权值和吗（如果单一标记权值为 1）？

再观察式子：

\sum_{i = 0}^x d(\operatorname{LCA}(i, u))

我们此时就有了 2 个思维方向：

以 u 作为主要枚举对象，对于每个 u，将 u 到根路径上的所有节点打上标记。再迭代到 x，统计答案。如果使用 HLD 维护，时间复杂度为 \mathcal{O}(n^2 \log^2 n)。
以 x 作为主要枚举对象，对于每个 i，将 i 到根路径上的所有节点打上标记。针对询问的 u，统计答案。如果使用 HLD 维护，时间复杂度为 \mathcal{O}((n + q) \log^2 n)。

显然，方向 2 更优秀，因为我们更好地处理了“前缀”。

本题采取的思维方向是一样的，但是，针对 k 次幂的处理，我们需要对点权做一次差分：

a(u) = d(u)^k - (d(u) - 1)^k

如此，由于差分，路径和就是 d(u)^k，而不是：

\sum_{i = 1}^{d(u)} i^k

综合题，但具有启发性。

我们思考如何判断 escape，显然，如果 (u, v) 均在 E 到 R 的路径上，就无法 escape。

但无法 escape 后，后面的问题就很困难了。

注意到，题目在强调 E 的特殊性！不妨考虑以 E 为根建树。escape 的判断略。

观察结构，我们可以发现，任何去商店的路径，都是从 R 走到祖先 x，再从 x 走到其子树内的商店。

设 t[u] 表示，u 到其子树内最近的商店的距离，用数学式子描述上述观察，为：max(t[x] + d[R] - d[x])。

当纯思考觉得不清晰时，务必写出数学表达式，如果没有写出 max(t[x] + d[R] - d[x])，后面的优化就不存在了。

将 d[R] 提出，得到 max(t[x] - d[x]) + d[R]。

考虑维护 t[x] - d[x]，设 f[x] = t[x] - d[x]，f 的求解是简单树上 DP，再使用树上倍增维护 f 即可。

注意点权在边界时的处理，如果 lift(u, k) 的 k = 0，答案应该为 f[0][u]，这说明什么？

等一下。