虚树：帮大树“减负”的神奇技巧

这是什么？用来干什么？

你见过一棵大树吗？比如家族族谱、电脑里的文件夹、或者一个国家的道路网——这些都可以用“树”这种结构来表示。树里有很多节点（点）和边（线），节点之间有父子关系。有时候，我们只关心树上的少数几个“关键点”，比如几个村庄、几个重要文件、或者几个需要查询的城市。但问题是：这些关键点之间的距离，往往要经过很多“中间点”（比如它们的祖先、或者路上的交叉口）。如果每次都在整棵大树上跑来跑去，那要访问太多不必要的节点，计算速度会非常慢。

能不能只保留这些关键点，以及它们之间“最重要”的连接？比如，只把关键点和它们两两之间的最近公共祖先（LCA，Lowest Common Ancestor）一起拿出来，重新连成一棵更小的树，但依然保留原来树上的祖先关系？这棵小树就叫虚树（Virtual Tree）。

生活中的类比

想象你有一张全国地图，上面标出了北京、上海、广州、成都四个城市。但地图上还有很多小县城、乡镇，你并不关心它们。你想知道这四个城市之间最直接的“高速公路”走向——其实只需要画出连接北京和上海、上海和广州、广州和成都……但这些路线可能会经过一些“大枢纽”（比如郑州、武汉）。这些枢纽就是原来树上的最近公共祖先。虚树就好比把地图上那些不重要的小城市全部擦掉，只留下你关心的城市和那些枢纽，然后用直线连起来——这样地图就变得很简洁，而且关键城市之间的相对位置（上下左右）依然正确。

虚树的核心概念

1. 哪些节点会出现在虚树里？

所有关键节点：比如你给出的那几个村庄。
每两个关键节点的最近公共祖先（LCA）：这些LCA可能原本不是关键点，但它们是在原树上连接关键点的“桥梁”。比如，村庄A和村庄B的LCA是镇子C，那么C也会被加入虚树，因为从A到B必须要经过C。
关键点数量为 $k$ ，那么虚树的节点数最多不超过 $2k$ （因为每两个点引入一个LCA，但多个LCA可能重复）。

2. 虚树要保留什么关系？

在虚树里，两个点之间如果有一条边，说明它们在原树上是一条“无分支的路径”（中间没有其他关键点或LCA）。也就是说，虚树上的边直接连接两个节点，并且这两个节点在原树上的路径上，除了端点以外，没有其他虚树节点。

3. 怎么构造虚树？

有一个非常经典的方法：先用DFS序把所有关键点排序，然后用一个栈来模拟“从根到当前节点的一条最右边链”。每次加入一个新节点时，通过LCA来调整栈，保证栈里始终是虚树中从根到当前节点的路径。

下面我们先来准备一些必要的工具，然后再看构造代码。

准备工作：DFS序、深度、LCA

为了构建虚树，我们需要知道每个节点的：

深度（depth）：从根到它的距离。
DFS序（dfn）：深度优先遍历时访问的顺序，时间戳。用来比较节点在树上的前后位置。越先被遍历到的节点，dfn越小。
最近公共祖先（LCA）：可以用倍增法快速求。

我们先用一个例子来建立这些信息。假设原树如下（根为1）：

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

先做一遍DFS，记录dfn、深度、父节点等。我们需要一个预处理函数 dfs 和求LCA的函数 lca。

完整示例：从排序到栈构建

下面给出一个可以运行的代码，包括预处理和虚树构建。关键点假设为 {4, 6, 7, 9}，我们来看看虚树会是什么样子。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;  // 最大节点数
int n, q;                 // n: 节点数, q: 查询次数
vector<int> G[MAXN];       // 原树邻接表
int dep[MAXN];            // 节点深度
int fa[MAXN][20];         // 倍增祖先，fa[u][i]表示u的第2^i祖先
int dfn[MAXN];           // DFS时间戳（顺序编号）
int tim;                 // 时间计数器

// 深度优先遍历，预处理深度、父节点、dfn
void dfs(int u, int father) {
    dep[u] = dep[father] + 1;   // 深度等于父亲深度+1
    fa[u][0] = father;          // 直接父亲
    dfn[u] = ++tim;             // 记录访问顺序
    for (int i = 1; i < 20; i++) {
        fa[u][i] = fa[fa[u][i-1]][i-1];  // 倍增预处理
    }
    for (int v : G[u]) {
        if (v != father) {
            dfs(v, u);
        }
    }
}

// 求u和v的最近公共祖先（倍增LCA）
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);   // 让u更深
    int diff = dep[u] - dep[v];
    // 让u跳到和v同一深度
    for (int i = 0; i < 20; i++) {
        if (diff & (1 << i)) {
            u = fa[u][i];
        }
    }
    if (u == v) return u;
    // 一起向上跳
    for (int i = 19; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

// ---------- 以下是虚树构建 ----------
vector<int> VG[MAXN]; // 虚树邻接表（注意每次使用前要清空）

// 构建虚树，nodes是给定的关键点列表（已去重）
void build_virtual_tree(vector<int>& nodes) {
    // 1. 按DFS序排序
    sort(nodes.begin(), nodes.end(), [](int a, int b) {
        return dfn[a] < dfn[b];
    });

    // 2. 用栈维护当前最右边链
    stack<int> st;
    st.push(nodes[0]);  // 第一个点入栈

    for (int i = 1; i < (int)nodes.size(); i++) {
        int u = nodes[i];           // 当前要加入的点
        int l = lca(u, st.top());   // 计算当前节点与栈顶的LCA

        // 如果LCA的深度小于栈顶节点的深度，说明栈顶不在LCA的子树内，
        // 需要不断弹出栈顶，并加边
        while (st.size() >= 2 && dep[l] <= dep[st.top()]) {
            int v = st.top(); st.pop();
            VG[st.top()].push_back(v);  // 将弹出的节点与新的栈顶连边
        }
        // 处理LCA和栈顶的关系
        if (dep[l] < dep[st.top()]) {
            VG[l].push_back(st.top());  // LCA与栈顶连边
            st.pop();                   // 弹出栈顶
            st.push(l);                 // LCA入栈
        }
        st.push(u);  // 当前节点入栈
    }
    // 最后，栈中剩下的节点连起来
    while (st.size() >= 2) {
        int u = st.top(); st.pop();
        VG[st.top()].push_back(u);
    }
    // 此时栈里还剩一个节点（虚树的根）
}

代码解释（按步骤）

步骤1：排序
为什么要按dfn排序？因为DFS序可以反映节点在树上的“左右顺序”。排序之后，相邻节点之间的LCA就是我们需要考虑的“叉路口”。

步骤2：栈的用法
栈里保存的是从虚树根到当前处理节点的一条路径（也就是虚树中还没处理完的最右边一条链）。开始时把第一个节点压入栈。

步骤3：处理每个新节点

计算新节点u与栈顶节点v的LCA l。
如果l的深度比栈顶浅，说明栈顶节点是l的后代，需要把栈顶弹出，并连一条从新栈顶到弹出节点的边（因为弹出节点应该连在新栈顶下面）。
但如果LCA比栈顶更浅，说明栈顶已经不属于l的子树了，需要弹出并处理LCA。
最后，确保LCA在栈中（如果不在则压入），然后压入u。

步骤4：收尾
遍历完所有节点后，栈里剩下的节点按顺序连成一条链，这就是虚树从根到最后一个节点的路径。

常见错误（新手容易踩的坑）

忘了对关键点去重和排序：如果不排序，构造会乱套；如果节点重复，会多出很多无意义的LCA。
栈操作顺序搞反：记得先弹出并连边，再考虑LCA是否该入栈。很多人的代码里while条件写错，或者忘记处理LCA与栈顶的深度比较。
虚树边方向搞错：一般我们把虚树建成有向边（从祖先指向后代）或者无向边，要根据后续DP需要决定。上面的代码中我们是从祖先向儿子加边。
没清空虚树邻接表：每次构建虚树前，要把上一次的VG清空，否则数据会叠加。
LCA预处理不完整：如果fa[][]没有预处理到根以上（根的父亲设为0或自己），求LCA时可能出错。
虚树根不一定是原树的根：如果关键点中没有包含根，那么虚树的根实际上是这些关键点的最高LCA（所有LCA的LCA），也就是通过栈处理后最后栈里剩下的那个节点。在上面的代码中，最后栈里剩下的就是虚树根。

完整可运行示例（含主函数）

下面给出一个完整例子，输入原树和一组关键点，输出构建的虚树边。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> G[MAXN];       // 原树
vector<int> VG[MAXN];      // 虚树（每次使用前清空）
int dep[MAXN], fa[MAXN][20], dfn[MAXN], tim;

void dfs(int u, int father) {
    dep[u] = dep[father] + 1;
    fa[u][0] = father;
    dfn[u] = ++tim;
    for (int i = 1; i < 20; i++) {
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (int v : G[u]) {
        if (v != father) dfs(v, u);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int i = 0; i < 20; i++) {
        if (diff & (1 << i)) u = fa[u][i];
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void build_virtual_tree(vector<int>& nodes) {
    // 清空虚树边
    for (int u : nodes) VG[u].clear();
    // 排序
    sort(nodes.begin(), nodes.end(), [](int a, int b) {
        return dfn[a] < dfn[b];
    });
    stack<int> st;
    st.push(nodes[0]);
    for (int i = 1; i < (int)nodes.size(); i++) {
        int u = nodes[i];
        int l = lca(u, st.top());
        while (st.size() >= 2 && dep[l] <= dep[st.top()]) {
            int v = st.top(); st.pop();
            VG[st.top()].push_back(v);
        }
        if (dep[l] < dep[st.top()]) {
            VG[l].push_back(st.top());
            st.pop();
            st.push(l);
        }
        st.push(u);
    }
    while (st.size() >= 2) {
        int u = st.top(); st.pop();
        VG[st.top()].push_back(u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 输入原树
    cout << "请输入节点数 n 和边数 n-1：\n";
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    // 从根节点1开始预处理
    dfs(1, 0);

    // 输入关键点数量
    cout << "请输入关键点个数：";
    int k;
    cin >> k;
    vector<int> key_nodes(k);
    cout << "请输入 " << k << " 个关键点：";
    for (int i = 0; i < k; i++) {
        cin >> key_nodes[i];
    }

    // 构建虚树
    build_virtual_tree(key_nodes);

    // 输出虚树上的边（假设虚树根为最后栈顶节点）
    cout << "虚树边（祖先->后代）：\n";
    // 先找到虚树根（通过遍历VG中所有节点，找出没有父亲的点？简单起见，我们记录所有出现在VG中的点）
    set<int> all_nodes;
    for (int u : key_nodes) {
        all_nodes.insert(u);
    }
    // 但LCA也可能不在key_nodes中，需要额外收集（这里简化，只输出已连接的边）
    for (int u = 1; u <= n; u++) {
        if (!VG[u].empty()) {
            for (int v : VG[u]) {
                cout << u << " -> " << v << "\n";
            }
        }
    }
    cout << "注意：以上可能只包含连边，根节点未标出。\n";

    // 清理（这里省略，实际多组数据时要清空全局数组）
    return 0;
}

运行示例

输入：

节点数 n = 9
边：
1 2
1 3
2 4
2 5
3 6
4 7
6 8
6 9
关键点：4 6 7 9

输出虚树边（可能形式，取决于具体实现）：

1 -> 2
1 -> 6
2 -> 4
2 -> 7
6 -> 9

解释：原树中，关键点4、7、9的LCA是2和1，6的LCA较大……最终虚树如图：

（注意7原本是4的子节点，但因为在虚树中2是4和7的公共祖先，所以7直接连到2；实际上7是4的子节点，但这里通过LCA，7的路径需要经过2，所以2->7。这是正确的虚树边：表示在原树上从2到7的路径上没有其他虚树节点。）

虚树 —— 只留重要节点的树