C++虚树算法详解（从零掌握虚树构建与应用）

为什么需要虚树？

假设你有一棵有 10⁵ 个节点的树，但每次查询只涉及 10 个关键点。如果每次都遍历整棵树，时间复杂度会很高（O(n)）。而通过构建虚树，我们只需在 O(k log k) 的时间内处理这 k 个关键点（k ≪ n），这就是树上问题优化的核心思想。

构建虚树的步骤

构建虚树的关键在于按 DFS 序排序关键点，并利用栈模拟 DFS 过程。以下是详细步骤：

1. 将关键点按 DFS 序（即进入时间戳 in[u]）升序排序
2. 将相邻关键点的 LCA 也加入集合（避免丢失祖先关系）
3. 再次按 DFS 序排序去重
4. 用栈维护当前虚树的右链（最右侧路径）
5. 依次加入每个点，根据 LCA 调整栈结构，建立父子关系

C++代码实现

下面是一个完整的 C++ 虚树构建模板，包含预处理 LCA 和虚树构建函数。这是算法竞赛技巧中的经典写法。

#include <bits/stdc++.h>using namespace std;const int N = 100010;const int LOG = 17;vector<int> g[N];int in[N], out[N], dep[N], fa[N][LOG];int timer = 0;// DFS 预处理 in, out, dep, favoid dfs(int u, int p) {    in[u] = ++timer;    dep[u] = dep[p] + 1;    fa[u][0] = p;    for (int i = 1; i < LOG; ++i)        fa[u][i] = fa[fa[u][i-1]][i-1];        for (int v : g[u]) {        if (v != p) dfs(v, u);    }    out[u] = timer;}// 判断 x 是否是 y 的祖先bool is_ancestor(int x, int y) {    return in[x] <= in[y] && out[y] <= out[x];}// 求 LCAint lca(int x, int y) {    if (is_ancestor(x, y)) return x;    if (is_ancestor(y, x)) return y;    for (int i = LOG - 1; i >= 0; --i) {        if (!is_ancestor(fa[x][i], y))            x = fa[x][i];    }    return fa[x][0];}// 构建虚树vector<int> build_virtual_tree(vector<int> key_nodes) {    // 去重    sort(key_nodes.begin(), key_nodes.end());    key_nodes.erase(unique(key_nodes.begin(), key_nodes.end()), key_nodes.end());        // 按 DFS 序排序    sort(key_nodes.begin(), key_nodes.end(), [&](int a, int b) {        return in[a] < in[b];    });        // 加入所有相邻点的 LCA    vector<int> tmp = key_nodes;    for (int i = 0; i < (int)tmp.size() - 1; ++i) {        key_nodes.push_back(lca(tmp[i], tmp[i+1]));    }        // 再次去重并按 DFS 序排序    sort(key_nodes.begin(), key_nodes.end());    key_nodes.erase(unique(key_nodes.begin(), key_nodes.end()), key_nodes.end());    sort(key_nodes.begin(), key_nodes.end(), [&](int a, int b) {        return in[a] < in[b];    });        // 用栈构建虚树    vector<int> stk;    vector<int> virtual_tree_nodes; // 返回虚树中的节点（可选）        for (int u : key_nodes) {        while (!stk.empty()) {            int w = stk.back();            if (is_ancestor(w, u)) {                // w 是 u 的祖先，连边 w -> u                // 此处可根据需要添加邻接表：virt_g[w].push_back(u);                stk.push_back(u);                break;            } else {                stk.pop_back();            }        }        if (stk.empty()) stk.push_back(u);    }        return key_nodes; // 返回虚树节点集合}

使用场景举例

虚树常用于以下类型的问题：

• 多次查询树上若干关键点的最小生成树（Steiner Tree）
• 动态规划只在关键点上进行（如 [NOI2015] 寿司晚宴）
• 求关键点之间的距离和、直径等

总结

通过本教程，你应该已经掌握了 C++虚树算法的基本原理和实现方法。记住：虚树不是真的新建一棵树结构，而是通过保留关键点及其 LCA，在原树信息基础上进行高效计算。掌握这一树上问题优化技术，将极大提升你在算法竞赛中的解题能力。

建议多练习相关题目（如 CF613D、BZOJ3572），巩固对算法竞赛技巧的理解。祝你编程顺利！