自动搬运

查看原文

来自洛谷，原作者为

	CrTsIr400 铬天铱

搬运于2025-08-24 21:56:32，当前版本为作者最后更新于2023-01-12 21:33:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种全新的虚树构造方法。

以往的虚树构建都是使用这样的方法：

• 把所有关键点按照 dfs 序排序，并且对相邻的两个点求出 LCA；
• 然后动态加入节点，维护一条动态的链。
• 这个过程可以使用单调栈维护从根节点到它的链。

但是，还不够简洁，也不够直观。

先前的做法已经利用了一个性质：

• 按照 dfs 序，排序之后，相邻的两个关键点的 LCA 一定不重不漏地覆盖了虚树上面的所有点。

那么不妨把虚树上的所有点求出来，再按照 dfs 序排序。

此时我们会发现如果按照 dfs 序，从小到大地枚举虚树上的点，可以发现当前点（设之为 $x$）和后面的点（设之为 $y$）的路径上，经过的节点的 dfs 序有两种情况：

• 如果 $y$ 是 $x$ 的后代，那么走过节点的 dfs 序会毫无例外地递增。因为这是一段往下走的旅程。

• 如果 $y$ 不是 $x$ 的后代，那么必然存在一段往上走、再往下走的旅程，设他们的 LCA 为 $z$，那么从 $x$ 到 $z$ 的过程中，dfs 序递减；而从 $z$ 到 $y$ 的过程之中，dfs 序递增。

通过分析这种情况，我们找到了一种虚树的构造方法：

• 对所有关键点 dfs 序排序，并且相邻求出 LCA，将 LCA 和关键点都存储在一个数组里；
• 将这个数组排序并且去重，目的是为了求出虚树上不重复的点按照 dfs 序排序的情况；
• 在虚树点数组里对相邻的两个点（设 dfs 序较小的节点标号为 $x$，较大的节点编号为 $y$ ）那么连接 LCA 和点 $y$ 。
• 然后虚树的构造过程就结束了！时间复杂度 $O(m\log m)$ ，其中 $m$ 为虚树点数。

那么证明为什么 dfs 序相邻的节点两两枚举，求得 LCA ，就能构建虚树了呢？

首先发现一个性质，$y$ 是 $x$ 往后第一个 dfn 序的节点，根据上文所提到的性质，dfn 序自 LCA 以来递增。

因为我们知道从 LCA 节点到 $y$ 的过程之中，点的 dfs 序在不断增大。

如果 LCA 和 $y$ 之间有节点 $p$ 的话，那么 $p$ 的 dfs 序必然小于 $y$ 的 dfs 序，而这显然是不符合排序顺序的。

所以，$y$ 和 LCA 之间没有重复的节点。

会不会有遗漏呢？我们发现按照这个构造流程，除了 dfs 序处于第一个的节点，其他都有连向它的边，所以正好构造一棵虚树。

虚树构建部分，具体的代码实现：（来自 OI-wiki ，另外 OI-wiki 那部分也是我补充的）

int dfn[maxn];
bool valid[maxn];
int h[maxn], m, a[maxn], len;  // 存储关键点
bool cmp(int x, int y) {
  return dfn[x] < dfn[y];  // 按照 dfn 序排序
}
void build_virtual_tree() {
  sort(h + 1, h + m + 1, cmp);  // 把关键点按照 dfn 序排序
  for (int i = 1; i < m; ++i) {
    a[++len] = h[i];
    a[++len] = lca(h[i], h[i + 1]);  // 插入 lca
  }
  a[++len] = h[m];
  sort(a + 1, a + len + 1, cmp);  // 把所有虚树上的点按照 dfn 序排序
  len = unique(a + 1, a + len + 1) - a - 1;  // 去重
  for (int i = 1, lc; i < len; ++i) {
    lc = lca(a[i], a[i + 1]);
    conn(lc, a[i + 1]);  // 连边，如有边权 就是 distance(lc,a[i+1])
  }
}

我之前只知道虚树能够解决怎样的问题，但是没有接触过虚树的构造方法，凭借 dfn 序的性质和画图分析，想出来了这种神奇的方法。

一开始我也不敢相信这是对的，于是在实验了数题之后，得出了结论；经过不断地思考，最后推导出来了它的正确性证明。

希望同学们能够大胆猜想，小心证明！