【问题求解II-HW3.B】砍树

树上任意两个点之间有且仅有一条简单路径。并且我们容易发现：如果要把两个点分到两棵树中，那么选择的这条边必须在连接这两个点的路径上。因此该问题被转化为了对树上的 $m$ 条路径求交。以下我们介绍三种做法供大家参考。

做法1: 基于LCA的路径标记

对于树上的任意两个点 $u$, $v$，从 $u$ 到 $v$ 的路径总可以被拆分为 $u\to lca(u, v)$ 和 $lca(u,v)\to v$ 两条直上直下的链。我们希望可以快速给链上所有的边打一个 +1 标记，这样最后只需要找有 $m$ 个标记的边即可。

如果对每条路径上的所有边暴力打 +1 标记的话，总复杂度为 $O(\sum_{i=1}^m len(u_i\to v_i))$，最坏情况下可以达到 $O(mn)$，不可接受。

以 $o(t)$ 的代价给 $t$ 条边打上标记似乎是一件“违反物理”的事情。但我们向大家展示如下的技巧做到这一点：

• 我们不把操作作用在边上，而是作用在点上，每个点与连向它父亲的边对应 (根节点没有对应的边)。
• 对于路径 $(u, v)$：
  • $mark(u) + 1$。
  • $mark(v) + 1$。
  • $mark(lca(u, v)) - 2$。
• 每个点最终的标记 $Mark(u) = \sum_{v\in subtree(u)} mark(v)$ (即以 $u$ 为根的子树中所有节点的 mark 之和)。

这个技巧有一个很炫酷的名字，叫“树上差分”。你可以对一条路径按照上述操作做一遍，然后验证一下处于各个位置的节点的 Mark，你会发现只有 $(u, v)$ 路径上的节点 (除了 LCA) Mark 为 1，其他的都是 0。这恰好符合我们在边上打标记的需求。此外，这个标记系统是可以累加的，即你不需要每次计算 Mark，而是可以把 $m$ 条边的 mark 做完之后再一起计算 Mark。这样我们在 $O(m+n)$ 的时间内完成了打标记的动作。加上预处理和计算 LCA 的复杂度，该算法的总时间复杂度为 $O((n+m)\log n)$。

做法2: 将树上路径求交转化为一维的区间求交

把第一个点对所在的路径 $(u_1, v_1)$ 抓出来，考虑剩下的 $m-1$ 条路径在 $(u_1, v_1)$ 上的相交部分。想象一下容易发现，如果把树中的一条链 $(u_1, v_1)$ 提出来，“用手拎着两端提在空中”，那么整个树的格局会像一个晾衣绳，晾衣绳上的每个点挂了一个树，如下图所示。

给 $(u_1, v_1)$ 这条链上的点重新标号 $x_1, x_2,\cdots, x_t$。对于其他任意一个点对 $(u_i, v_i)$，如果 $u_i, v_i$ 在同一个 $x_p$ 的树下 (如图中红色所示)，那么 $(u_i, v_i)$ 这条路径将完全在 $x_p$ 的子树内部，从而和 $(u_1, v_1)$ 没有边的交集；如果 $u_i, v_i$ 在不同的子树 $x_p, x_q (p<q)$ 下 (如图中蓝色所示)，那么 $(u_1, v_1)$ 和 $(u_i, v_i)$ 这两条链将会有 $(x_p, x_q)$ 这一段是公共的。

对于 $(u_2, v_2), \cdots, (u_m, v_m)$ 中的每一对，我们都可以检查 $u_i, v_i$ 在哪棵子树中，从而算出它和 $(u_1, v_1)$ 的交集。这时问题已经被转化成了在一维序列 $x_1, \cdots, x_t$ 上的区间交集问题。剩下的一点点细节非常简单，留给大家思考。

这个做法颇有“大道至简”的意味——没有“倍增求LCA”“树上差分“这样炫酷的技术，就是平平无奇的几遍搜索，就给出了更优秀的时间复杂度 $O(n)$。在这里我们也想给大家传递一个价值观：

高级算法和高级数据结构就像武林中的重武器，而你分析问题、转化问题的能力则像内功。内功和武器是相辅相成的，内功不足却想耍大刀，适得其反。比起盲目地学习很多炫酷的技术，我们更希望大家能充分锻炼自己的思维能力，这才是成为一个优秀的算法设计师的正道。

做法3: 一个神奇的随机算法

这个做法有些“过于”精巧，大家只需欣赏即可。

为每个数对 $(u_i, v_i)$ 随机一个数 $c_i$，并将 $c_i$ 打在 $u_i, v_i$ 两个节点上。对于每条边，砍掉它合法的充分必要条件是这条边下面的子树恰好包含 $c_1, c_2, \cdots, c_m$ 各一个。这件事并不容易检查，但我们直接对子树上的数值求异或和，并通过检查子树异或和是否等于所有 $c_i$ 的异或和的方式来“判定”子树是否满足要求。时间复杂度 $O(n)$。

看上去有点雷人。下面尝试用不太严谨的方式论证该做法错误的概率极小：

异或的性质是：$x\otimes x = 0$ (其中 $\otimes$ 常用于表示异或算符)。因此如果一个子树同时包含了一对点 $(u_i, v_i)$ 中的两个或零个，那么它最终的异或和将缺少 $c_i$ 这一项。因此要使得上述随机算法错误，一定存在一个 $\{1, 2, \cdots,m\}$ 的子集 $\{k_1, k_2, \cdots k_t\}$ 满足 $\bigotimes_{i=1}^t c_{k_i} = 0$，且恰好存在一条边能把这个子集精准地“选出来”。

对于一个集合，若该集合中的数在 $[0, 2^k)$ 之间随机，那么不论这个集合中元素的个数有多少，该集合的异或和为 0 的概率都是 $\frac{1}{2^k}$ (考虑每个二进制位，有若干个要么是 0 要么是 1 的数，但不论有多少，其中有偶数个 1 的概率都是 $\frac{1}{2}$)。

我们可以不严谨地认为，树上的每条边相当于独立地在 $\{1, 2, \cdots, m\}$ 中选一次子集 (说它不严谨是因为 ①不同的边选出的集合之间存在互相包含关系，并不是独立的； ②该过程和 $2m$ 个数在树上的分布有关，并不是随机选取。但总体可以感受到在概率上两者是同阶的)。因此该算法正确的概率

$$ P(correct)\sim \left(1-\frac{1}{2^k}\right)^{\min(2^m, n)} $$

本题中 $n\sim 10^5$。简单计算可知，当 $k=32$ 时正确率已经达到 $99.997\%$，当 $k=64$ 时该算法正确率将极其接近 $100\%$ (64位恰好是 long long 的范围，在 long long 范围内随机整数并不困难)。

虽然从理论计算科学的角度，有错误率的随机算法和确保正确的算法之间存在本质区别，但在实际中，如果算法错误的概率已经远小于硬件出错的概率，那么该算法的可用性便已经很高。对于这道题来说，我们确实容易设计出简单高效的线性算法，但事实上，绝大多数问题是难的 (关于难的定义，以及 P, NP, NP-hard 相关的概念大家会在第四学期学习)，对于难问题，很多时候我们只能从近似角度尝试解决。