055-图论-虚树构建

1. 核心概述 在已预处理 LCA 的根树上，对给定关键点集合 S 通过加入必要的两两 LCA 并压缩边，构造覆盖它们的最小包含树（虚树），整体 O(|S| log |S|)。

2. 原文引述

Description: Given a rooted tree and a subset S of nodes, compute the minimal subtree that contains all the nodes by adding all (at most $|S|-1$) pairwise LCA’s and compressing edges. Returns a list of (par, orig_index) representing a tree rooted at 0. Time: $O(|S|\log |S|)$

3. 展开阐述

• 定义与背景

  • 虚树（Virtual Tree）：在原树不变的前提下，仅以 S 中的关键点及其必要的公共祖先为节点、以原树中的唯一路径压缩为边，形成规模远小于原树的“任务相关”子树。
  • 典型适用：多次离线/在线对不同 S 做路径/子树类统计（如覆盖次数、距离和、DP 聚合），通过在虚树上进行线性或近线性处理显著降本。

• 接口/字段/数据结构（据实现约定）

  • vpi compressTree(LCA& lca, const vi& subset)
    • 输入：lca 为已构建的 LCA 结构；subset 为关键点集合（节点编号）。
    • 输出：vector<pair<int,int>>，每项为（par, orig_index），表示“新索引节点的父在新索引空间中的编号、该新节点对应的原树节点编号”。根节点父指向自己。
  • 依赖：需要原树的 DFS 序/入时刻与 LCA 查询接口 lca.lca(u,v)。

• 核心流程/要点（排序 + 插入 LCA + 压缩构建）

  1. 关键点预处理
     • 去重 subset 并按 DFS 进入时间 in[u] 从小到大排序，得到序列 li。
  2. 插入必要 LCA
     • 遍历相邻对 (li[i], li[i+1])，将它们的 LCA 插入集合；再去重并按 in 重新排序。
     • 直觉：原树上“相邻 DFS 序点”的唯一路径只可能在二者的 LCA 处分叉，加入即可保证连通性且数量至多 |S|-1。
  3. 建立新索引映射
     • rev[orig] = 新索引，形成紧凑的 0..k-1 节点空间，便于返回与后续算法。
  4. 构建虚树边（栈/单调链法）
     • 线性扫描 li：维护一条“当前右端为 li[i] 的最小链”栈。
     • 对当前点 u，令 p = LCA(u, 栈顶)，不断弹栈直至 p 成为栈顶的祖先；将被弹出的顶 v 以父=新栈顶连接；若 p 未在栈中则插入 p。
     • 最后将残余栈相邻连边。亦可按实现注释的“相邻取 LCA 直接连父→子”的更简方案（两者等价）。
  5. 压缩与语义
     • 虚树边权可继承为“原树上两端距离/路径聚合值”，以承载 DP 或计算（例如计数覆盖时用 dist/size 等）。

• 复杂度与边界条件

  • 排序/去重 O(|S| log |S|)；每个节点入栈出栈至多一次，整体线性；多次 LCA 查询总计 O(|S| log N) 或 O(|S|)（若用 RMQ-LCA）。
  • 规模上界：加入的 LCA 至多 |S|-1，虚树节点数 ≤ 2|S|-1；边数为节点数减一。
  • 非同一连通分量/森林：需要统一虚根或保证 S 都在同一树内；二进制提升约定“根的父为自身”可安全处理边界。
  • 重复点/包含关系：排序+去重后自然规避；若某关键点是另一关键点祖先，仍保留为虚树节点，边压缩为直接父子。

• 变体/扩展

  • 搭配二进制提升 054-图论-二进制提升：以 O(log N) 求 LCA；若频繁构建虚树，亦可用 RMQ-LCA 减小常数。
  • 在虚树上做 DP：例如统计 S 中点对路径长度和、被覆盖次数、带权计数等，虚树结构避免访问与 S 无关的大量原树节点。
  • 多集合批处理：若需要对多组 S 重复构建虚树，可复用排序与 LCA 结果，甚至共享一个可重置的小型邻接存储池。

• 正确性要点与不变式

  • 最小性：插入的仅是相邻关键点的 LCA；由“DFS 序与 LCA 的祖先区间”性质，能保证连通且不引入冗余节点。
  • 无重边/无交叉：按 DFS 序与单调栈连接保证得到一棵树（层次与祖先关系单调），每条原树路径在虚树中被唯一承载。
  • 距离/聚合一致性：若边权设置为原树距离，则任意两点在虚树上的距离等于原树上的距离，保证后续 DP/计数结果一致。

• 与相邻技术对比与取舍

  • 与直接在原树上做多次路径合并相比：虚树规模远小，能将复杂度降到与 |S| 成正比。
  • 与重链剖分 066-图论-重链剖分：HLD 适合路径分段+数据结构；虚树适合“以关键点为骨架”的一次性或批量计算。
  • 与在线查询 LCA 068-图论-最近公共祖先：虚树依赖高效 LCA；若查询稠密、S 稀疏，虚树更具优势。

4. 关联节点

• 068-图论-最近公共祖先
• 054-图论-二进制提升
• 066-图论-重链剖分