华硕笔记本风扇异常怎么修：G-Helper 5分钟校准风扇曲线完整指南
2026/9/11 11:10:03
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） stack<int> 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; vector<int> 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(vector<int>& keys) { vector<int> nodes = keys; // 加入相邻关键节点的 LCA for (int i = 0; i+1 < keys.size(); i++) { int l = lca(keys[i], keys[i+1]); 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()); stack<int> 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，特别适用于多次查询、动态规划等场景。掌握虚树的构建原理和实现细节，能够显著提升解决复杂树上问题的能力。