C语言虚树算法详解（从零开始掌握高效处理树上查询的技巧）

虚树的应用场景

• 多次查询只涉及少量关键点的树形DP问题
• 树上最短路径聚合（如求关键点间最小生成树）
• 优化大规模树上的交互式问题

构建虚树的基本步骤

构建虚树通常包含以下几个核心步骤：

1. 收集所有关键点
2. 按DFS序对关键点排序
3. 将相邻关键点的LCA也加入集合（去重）
4. 再次按DFS序排序
5. 使用栈模拟DFS过程，构建虚树边

C语言实现虚树构建

下面是一个完整的C语言代码示例，演示如何构建虚树。我们假设已经通过预处理获得了每个节点的深度、父节点和DFS序。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 100010#define LOG 17int n, m;int head[MAXN], to[MAXN << 1], nxt[MAXN << 1], ecnt = 1;int dep[MAXN], fa[MAXN][LOG + 1], dfn[MAXN], clk;int key[MAXN], stk[MAXN], top;int vhead[MAXN], vto[MAXN << 1], vnxt[MAXN << 1], vecnt;void add_edge(int u, int v) {    to[ecnt] = v;    nxt[ecnt] = head[u];    head[u] = ecnt++;}void dfs(int u, int f) {    dfn[u] = ++clk;    dep[u] = dep[f] + 1;    fa[u][0] = f;    for (int i = 1; i <= LOG; i++)        fa[u][i] = fa[fa[u][i - 1]][i - 1];    for (int i = head[u]; i; i = nxt[i]) {        int v = to[i];        if (v == f) continue;        dfs(v, u);    }}int lca(int u, int v) {    if (dep[u] < dep[v]) { int t = u; u = v; v = t; }    for (int i = LOG; i >= 0; i--)        if (dep[fa[u][i]] >= dep[v])            u = fa[u][i];    if (u == v) return u;    for (int i = LOG; i >= 0; i--)        if (fa[u][i] != fa[v][i])            u = fa[u][i], v = fa[v][i];    return fa[u][0];}int cmp(const void *a, const void *b) {    return dfn[*(int*)a] - dfn[*(int*)b];}void build_virtual_tree(int k) {    for (int i = 0; i < k; i++)        key[i] = /* 输入的关键点 */;    qsort(key, k, sizeof(int), cmp);    int tmp[MAXN], cnt = 0;    for (int i = 0; i < k; i++)        tmp[cnt++] = key[i];    for (int i = 0; i < k - 1; i++)        tmp[cnt++] = lca(key[i], key[i + 1]);    // 去重并重新排序    qsort(tmp, cnt, sizeof(int), cmp);    cnt = 1;    for (int i = 1; i < cnt; i++)        if (tmp[i] != tmp[i - 1])            tmp[cnt++] = tmp[i];    // 构建虚树    top = 0;    vecnt = 1;    memset(vhead, 0, sizeof(vhead));    stk[top++] = tmp[0];    for (int i = 1; i < cnt; i++) {        int u = tmp[i], p = lca(stk[top - 1], u);        while (top > 1 && dep[stk[top - 2]] >= dep[p]) {            // 添加边 stk[top-2] -> stk[top-1]            vto[vecnt] = stk[top - 1];            vnxt[vecnt] = vhead[stk[top - 2]];            vhead[stk[top - 2]] = vecnt++;            top--;        }        if (stk[top - 1] != p) {            vto[vecnt] = stk[top - 1];            vnxt[vecnt] = vhead[p];            vhead[p] = vecnt++;            stk[top - 1] = p;        }        stk[top++] = u;    }    while (top > 1) {        vto[vecnt] = stk[top - 1];        vnxt[vecnt] = vhead[stk[top - 2]];        vhead[stk[top - 2]] = vecnt++;        top--;    }}int main() {    // 初始化原树，调用 dfs(1, 0) 预处理    // 然后根据查询调用 build_virtual_tree(k)    return 0;}

注意事项与优化建议

1. 虚树中的边权通常不是原树中的边权，而是两点在原树中的距离，需额外计算。
2. 每次构建虚树前记得清空虚树的邻接表。
3. 关键点数量 k 通常远小于 n，因此虚树的节点数不超过 2k。
4. 在实际应用中，常配合C语言图论算法（如树形DP、最短路）一起使用。

总结

通过本文的学习，你应该已经掌握了高效处理树上查询的利器——虚树算法。虽然初次接触可能觉得复杂，但只要理解了其“保留关键路径、压缩无关分支”的核心思想，就能灵活运用于各类树形问题中。

记住，掌握C语言虚树算法不仅能提升你的编程能力，还能在算法竞赛中助你一臂之力！快动手试试吧！