P4103 [HEOI2014] 大工程题解

SMT0x400 · 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 序的性质和画图分析，想出来了这种神奇的方法。

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

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

P4103 [HEOI2014] 大工程 题解

P4103 [HEOI2014] 大工程题解