虚树（Virtual Tree / Auxiliary Tree）#

1. 定义#

虚树用于处理“树上多次查询，每次只关心少量关键点”的问题。

给定原树上的一组关键点 key_nodes，虚树会：

• 保留所有关键点
• 补上必要的 LCA
• 只保留这些点之间的祖先关系

最终得到一棵规模远小于原树的“浓缩树”。

它的意义是：

• 原来一次查询可能要扫整棵树，复杂度接近 O(N)
• 用虚树后，只需要在与关键点相关的极少数节点上做 DP / 统计

2. 适用场景#

典型特征：

• 原图是一棵树
• 有很多组询问
• 每次询问只给出 K 个关键点
• 需要在这些关键点之间做路径、覆盖、DP、贡献统计

常见题型：

• 树上关键点最短连通子图
• 树上路径覆盖 / 染色 / 切断类 DP
• 一组点之间的距离和、边权贡献
• 每次只对少量特殊点做转移的树形 DP

3. 核心性质#

1
2K - 1

1
dist[son] - dist[fa]

4. 预处理前提#

构建虚树前，原树必须先支持以下信息：

• dfn[u]：DFS 序
• depth[u]：节点深度
• get_lca(u, v)：能快速查询 LCA

常见 LCA 实现：

• 倍增 LCA
• Euler Tour + RMQ
• 树剖求 LCA

5. 这份模板做了什么#

模板接口：

1
int build(std::vector<int> key_nodes,
2
          const std::vector<int>& dfn,
3
          const std::vector<int>& depth,
4
          const std::function<int(int, int)>& get_lca)

返回值：

• 返回虚树根节点编号

结果存储：

• graph[u]：虚树中 u 向下连到哪些儿子
• used_nodes：本次构建用到的所有节点，便于下次 O(K) 清空

注意这份实现的一个细节：

• 函数参数是 std::vector<int> key_nodes
• 这是按值传参
• 所以函数内部确实会排序、去重
• 但不会修改调用者手里的原数组

也就是说，代码行为比注释更安全。

6. 为什么按 DFN 排序#

虚树构造的核心前提是：

1
std::sort(key_nodes.begin(), key_nodes.end(),
2
          [&](int u, int v) { return dfn[u] < dfn[v]; });

原因：

• 按 DFS 序排序后，关键点在原树上的出现顺序与“子树区间”一致
• 相邻关键点之间的 LCA 足以恢复整棵虚树结构
• 配合单调栈，可以只维护一条“当前右链”

这是整套做法成立的基础。

7. 单调栈在维护什么#

栈中维护的是：

• 当前已经处理过的点
• 在虚树中尚未完成连边的那条祖先链

可以把它理解成：

• 栈底更高
• 栈顶更深
• 栈里节点的 dfn 单调递增
• 同时它们在原树上形成一条“右边界链”

每来一个新点 u：

1. 求 lca = LCA(u, stk.back())
2. 如果 lca 在栈顶上方，说明要把一些点先退栈并连边
3. 必要时把 lca 作为新的分叉点插入栈
4. 再把 u 入栈

8. 模板流程拆解#

1
for (int u : used_nodes) {
2
    graph[u].clear();
3
}
4
used_nodes.clear();

1
std::sort(key_nodes.begin(), key_nodes.end(),
2
          [&](int u, int v) { return dfn[u] < dfn[v]; });
3

4
key_nodes.erase(std::unique(key_nodes.begin(), key_nodes.end()), key_nodes.end());

1
std::vector<int> stk;
2
stk.push_back(key_nodes[0]);
3
used_nodes.push_back(key_nodes[0]);

1
int u = key_nodes[i];
2
int lca = get_lca(u, stk.back());

1
while (stk.size() > 1 && depth[stk[stk.size() - 2]] >= depth[lca]) {
2
    graph[stk[stk.size() - 2]].push_back(stk.back());
3
    stk.pop_back();
4
}

1
if (depth[stk.back()] > depth[lca]) {
2
    graph[lca].push_back(stk.back());
3
    stk.pop_back();
4

5
    if (stk.empty() || stk.back() != lca) {
6
        stk.push_back(lca);
7
        used_nodes.push_back(lca);
8
    }
9
}

1
stk.push_back(u);
2
used_nodes.push_back(u);

1
while (stk.size() > 1) {
2
    graph[stk[stk.size() - 2]].push_back(stk.back());
3
    stk.pop_back();
4
}

1
return stk[0];

9. 为什么这棵树是“有向树”#

模板里建边方式是：

1
graph[parent].push_back(child);

也就是说方向固定为：

• 父节点指向子节点

这样做的好处是：

• 直接适配树形 DP
• 不需要再带父节点参数防止走回头路
• 单次查询构出的图天然就是一棵 rooted tree

10. 复杂度要说准确#

这份模板常被口头写成 O(K log K)，但严格来说应分开看：

• 排序：O(K log K)
• 去重：O(K)
• 单调栈建树：O(K)
• LCA 查询：一共 O(K) 次，每次代价取决于你的 LCA

因此总复杂度更准确地写成：

1
O(K log K + K * T_lca)

若：

• LCA = O(1)，则整体是 O(K log K)
• LCA = O(log N)，则整体是 O(K log K + K log N)

11. 使用方式#

假设你已经对原树完成了 DFS 和 LCA 预处理：

1
int n = ...;
2
VirtualTree vt(n);
3

4
std::vector<int> key_nodes = {5, 9, 13, 20};
5

6
int root = vt.build(
7
    key_nodes,
8
    dfn,
9
    depth,
10
    [&](int u, int v) {
11
        return lca(u, v);
12
    }
13
);
14

15
// 在虚树上做 DP
16
std::function<void(int)> dfs = [&](int u) {
17
    for (int v : vt.graph[u]) {
18
        dfs(v);
19
    }
20
};
21

22
dfs(root);

如果题目需要知道“哪些点是原始关键点”，通常会额外维护：

1
is_key[u] = true / false

然后在虚树 DP 时区分：

• 原始关键点
• 补出来的 LCA 点

12. 例子理解#

设原树中查询关键点是：

1
{4, 5, 8, 9}

它们在原树上的结构大致是：

1
        1
2
      /   \
3
     2     3
4
    / \   / \
5
   4   5 8   9

那么虚树中需要保留的点是：

1
{4, 5, 8, 9, 2, 3, 1}

虚树结构就是：

1
        1
2
      /   \
3
     2     3
4
    / \   / \
5
   4   5 8   9

如果一组关键点本来几乎都落在同一条链上，虚树会更小。

比如关键点是：

1
{10, 15, 18}

而这三个点祖先链很接近，那么虚树可能只包含少量补点。

13. 常见坑#

14. 记忆版总结#

• 虚树 = 关键点 + 必要 LCA 的浓缩树
• 构造顺序：dfn 排序 -> 去重 -> 单调栈建树
• 栈维护的是当前未完成连边的祖先链
• 虚树规模最多 2K - 1
• 单次构造复杂度是 O(K log K + K * T_lca)
• 模板中的边是“父 -> 子”的有向边，适合直接做树形 DP