1. 什么是虚树虚树Virtual Tree是一种用于优化树上动态规划DP或查询的算法技巧。它通过提取原树中与当前问题相关的关键节点如查询点、特殊点等构建一棵规模更小的新树从而将问题规模从 O(n) 降低到 O(k)k 为关键节点数量显著提升算法效率。虚树的核心思想是只保留关键节点以及它们之间的最近公共祖先LCA删除所有无关的节点和边形成一棵保持原树关键节点相对祖先-后代关系的简化树。2. 虚树的构建原理2.1 关键节点Key Nodes关键节点通常包括查询点需要处理或回答的节点特殊标记点如资源点、危险点等任意指定的节点集合2.2 构建步骤虚树的构建通常遵循以下流程预处理使用 DFS 预处理原树得到每个节点的深度depth、DFS 序dfn以及用于快速求 LCA 的数据结构如倍增表、树链剖分等。关键节点排序将所有关键节点按照 DFS 序从小到大排序。添加 LCA将排序后相邻关键节点的 LCA 加入节点集合避免重复。再次排序将所有节点关键节点 LCA按 DFS 序排序。栈构建法建树使用栈维护当前虚树的右链按 DFS 序依次加入节点通过比较深度确定父子关系。3. 虚树的构建算法栈方法以下是使用栈构建虚树的经典算法伪代码描述// 假设 nodes 为已按 dfn 排序的关键节点包含必要的 LCA stackint stk; stk.push(nodes[0]); // 根节点入栈 for (int i 1; i nodes.size(); i) { int u nodes[i]; int lca getLCA(u, stk.top()); while (stk.size() 1 depth[stk.top()] depth[lca]) { int v stk.top(); stk.pop(); // 添加边 (stk.top(), v) 到虚树 addVirtualEdge(stk.top(), v); } if (depth[stk.top()] depth[lca]) { // 处理栈顶是 lca 后代的情况 int v stk.top(); stk.pop(); addVirtualEdge(lca, v); if (stk.empty() || stk.top() ! lca) { stk.push(lca); } } stk.push(u); } // 清空栈构建剩余边 while (stk.size() 1) { int v stk.top(); stk.pop(); addVirtualEdge(stk.top(), v); }4. 虚树的应用场景4.1 树上动态规划优化典型问题一棵树上有若干个特殊点需要计算每个节点到最近特殊点的距离或处理覆盖、连通等问题。如果对每个查询都做一次 O(n) 的树形 DP当查询很多时会超时。使用虚树可以将每次查询的复杂度降至 O(k log n)k 为查询点数量。4.2 多次查询路径相关问题例如多次询问树上某条路径的权值和、最大值等。如果预处理后能在 O(1) 或 O(log n) 回答两点间信息那么对一组查询点构建虚树后可以在虚树上快速处理所有查询。4.3 资源分配与连通性检查在游戏或网络设计中某些资源只存在于特定节点需要快速判断一组节点是否连通或者计算连通块数量。虚树可以帮助快速缩点并分析结构。5. 时间复杂度分析预处理DFS 和 LCA 预处理 O(n log n)。单次虚树构建O(k log k)排序 O(k log n)求 LCA。在虚树上 DP/查询O(k)。总复杂度从 O(n × q) 优化到 O((n Σk_i) log n)其中 q 是查询次数k_i 是第 i 次查询的关键节点数。6. 代码示例C 实现片段#include bits/stdc.h using namespace std; const int N 1e5 5, LOG 17; vectorint g[N], vt[N]; // 原树虚树 int depth[N], fa[N][LOG], dfn[N], timer; void dfs(int u, int p) { dfn[u] timer; depth[u] depth[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); } int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); for (int i LOG-1; i 0; i--) if (depth[fa[u][i]] depth[v]) u fa[u][i]; if (u v) return u; for (int i LOG-1; i 0; i--) if (fa[u][i] ! fa[v][i]) u fa[u][i], v fa[v][i]; return fa[u][0]; } // 构建虚树keys 为关键节点列表已按 dfn 排序 void buildVirtualTree(vectorint keys) { vectorint nodes keys; // 加入相邻关键节点的 LCA for (int i 0; i1 keys.size(); i) { int l lca(keys[i], keys[i1]); nodes.push_back(l); } sort(nodes.begin(), nodes.end(), [](int a, int b) { return dfn[a] dfn[b]; }); nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end()); stackint stk; stk.push(nodes[0]); for (int i 1; i nodes.size(); i) { int u nodes[i]; int l lca(u, stk.top()); while (stk.size() 1 depth[stk.top()] depth[l]) { int v stk.top(); stk.pop(); vt[stk.top()].push_back(v); } if (depth[stk.top()] depth[l]) { int v stk.top(); stk.pop(); vt[l].push_back(v); if (stk.empty() || stk.top() ! l) stk.push(l); } stk.push(u); } while (stk.size() 1) { int v stk.top(); stk.pop(); vt[stk.top()].push_back(v); } }7. 注意事项与常见问题根节点的选择虚树需要指定根节点通常选择关键节点中深度最小的节点或原树的根。边权的处理虚树中的边可能需要携带原树路径上的信息如距离、最小值等需要在构建时计算。多次查询的清空每次构建虚树后需要清空虚树的邻接表避免影响下一次构建。LCA 的预处理使用倍增、树链剖分或 RMQ 等方法实现 O(log n) 的 LCA 查询。8. 总结虚树是一种强大的树上问题优化工具它通过提取关键节点构建简化树将问题规模从节点总数 n 降低到关键节点数 k特别适用于多次查询、动态规划等场景。掌握虚树的构建原理和实现细节能够显著提升解决复杂树上问题的能力。