虚树学习笔记 | Sengxian's Blog

虚树学习笔记 | Sengxian's Blog

可以看到，所有关键点都留了下来，而且树的形态也被完好的保存了下来。往往未被选中的点并不影响答案，这些未被选中的点，以路径长度的形式存在于虚树中。

定理一：在一棵有根树中，任选 $k$ 不重复的点，这 $k$ 个点两两之间的不同的 LCA 个数不超过 $k - 1$ 个。
证明：我们考虑求出 $k$ 个点两两之间的 LCA，将其按照到根的距离从到大到小排序，记为 $l_1, l_2, \cdots, l_m$。

我们考虑这样一个事实：假设 $u$ 和 $v$ 的 LCA 是 $l_1$，而如果 $u$ 与 $w$ 的 LCA 是 $l_x$ 且 $l_x \neq l_1$，那么 $v$ 与 $w$ 的 LCA 也是 $l_x$。考虑反证法，如果 $v$ 与 $w$ 的 LCA 不是 $l_x$ 的话，那么 $l_x$ 必然在 $l_1$ 的子树中，由于 $x > 1$，所以 $l_x$ 到根的距离必然小于 $l_1$ 到根的距离，这与「$l_x$ 在 $l_1$ 的子树中」这一事实矛盾。

基于这一个事实，我们可以发现，所有 LCA 是 $l_1$ 的一堆点，都可以被看作一个点（每个点对之后的 $l$ 的贡献都是一样的）。所以对于 $l_2$ 来说，可考虑的点就至多只有 $k - 1$ 个了。同理，所有 LCA 是 $l_2$ 的一堆点，又可以被看作一个点。所以对于 $l_3$ 来说，可考虑的点就至多只有 $k - 2$ 个了。一直压缩下去，对于 $l_{k - 1}$ 来说，可以考虑的点就至多只有 $2$ 个了。至于 $l_k$ 至多只有一个点可考虑，无法形成新的 LCA。所以 $l_k$ 不可能存在。

Read full article from 虚树学习笔记 | Sengxian's Blog