牛客 5278G 这道题，题名叫“血压游戏”，出自某高校第18届网络友谊赛。我当时在群里看到它的标签是“虚树+dp”，第一反应就是：这题怕不是要把人血压搞高。实际做下来也确实是，树形DP人人会写，但一旦套上虚树，很多选手的代码就开始在边界上面翻车：栈弹多了、LCA 算错、负血量没夹断、虚树边权忘了按深度差折算。这篇文章不是简单地贴一份 AC 代码，而是把这套“虚树+DP”经典题背后的思考过程完整拆开。虚树解决的是一类核心矛盾：原树很大，但每次真正参与计算的“关键点”很少。比如整棵树有 1e5 个点，询问有 1e5 次，但每次询问涉及的点数总和有限，这种情况下朴素树形DP必然超时，虚树才是正解。适合的读者是已经会基础树形DP和 LCA、想彻底搞懂虚树构建和落地细节的朋友，下面按一条从读题到 AC 的完整线索来讲。

1. 看到“血压游戏”，先判断这是不是一道虚树题

1.1 哪些“信号”在暗示虚树

我挑几个最典型的信号。第一，题面出现“每次给出一个点集”，比如“每次选择 m 个节点作为关键点”。第二，题目里出现“所有关键点的血量/贡献向上汇聚”之类的表述，也就是需要在树上做某种汇总型DP。第三，也是最关键的一个约束：所有询问的“关键点总数”会被限制在一个可以接受的范围，常见写法是 Σk ≤ 2e5，或者“所有询问涉及的点两两不同”。

为什么看到这三个信号就要往虚树上想？因为虚树就是为“多次询问、关键点稀疏、但每次都要做全树相关 DP”这种场景设计的。如果每次询问都老老实实把整棵 n 个点的树扫一遍，那复杂度就是 O(nq)，随便一组数据就能让你跑到天荒地老。而虚树的做法是把每次询问只用到的 O(k) 个节点单独抽出来，重新拼成一个小规模的树，在这个小树上跑等价的 DP，复杂度直接降到 O(k log k) 级别。

1.2 复杂度陷阱：为什么朴素树上DP会挂

直接算一下就能感受到差距。假设 n=1e5，q=1e5，每次询问给 k 个关键点，且 Σk=2e5。朴素做法是一次询问做一次完整树上DP，复杂度 O(n)，那么总复杂度是 O(nq)=1e10，这还没算递归和常数，放在任何在线评测系统里基本都是超时的命。就算你把 DP 写成递推或者加剪枝，最坏情况依然救不回来。

虚树方案的总复杂度是 O(Σk log k)，因为每次构建虚树要排序关键点、求相邻点的 LCA，这部分是 O(k log n)，虚树上的 DP 是 O(k)，把所有询问加起来就是 O(Σk log k)。这个复杂度在 Σk 有限的情况下非常舒服。所以这道题的“血压游戏”表面上在考树形DP，实际上是在考你能不能识别出“关键点稀疏”这个题眼，然后果断上虚树。

1.3 虚树的本质：压缩但不丢失结构

说句大白话，虚树就是一张“折叠地图”。你要开车从几个城市到总部，路线沿途要经过很多小镇，但你不需要把每个小镇都画在地图上，只需要知道城市之间的距离。虚树保留的正是关键点之间的拓扑关系，把中间那些“纯路过”的节点整条链压成一条边，边的长度用深度差来表示。

这里有个重要的点：虚树没有丢失任何 DP 需要的信息。对于一个树形DP，真正影响转移结果的无非是每个节点的状态、父子关系、以及路径上的累积代价。虚树把非关键点的状态浓缩成路径长度，因为一路上的损耗只和总长度有关，不需要知道中间某个点长什么样。这就是它能做到 O(k) 点数却和原树等价的根本原因。

2. 虚树怎么建：排序、LCA、单调栈一次讲透

2.1 保留什么、丢掉什么，以及最多多少个点

虚树的点集其实由两部分组成：本次询问的关键点，以及这些关键点之间必要的 LCA。为什么 LCA 必须出现？因为两个关键点可能位于两棵不同的子树分支上，它们的信息要向上汇聚，就一定要在 LCA 这个位置碰头。就算 LCA 本身不是关键点，它也必须作为一个汇合点出现在虚树里，否则两条分支的贡献接不上。

一个常用的结论：如果一共有 k 个关键点，把它们按 DFS 序排序，再把相邻两个关键点的 LCA 全部加入，最终虚树的节点数不超过 2k-1。这个结论的直观解释是，k 个叶子节点构成的一棵压缩树，内部节点的数量不会超过叶子数量减一。所以虚树的空间开销很小，这也是它能跑大量询问的基础。

2.2 构建步骤：按DFS序排序加维护右链

构建虚树我固定用四步走。第一步，把关键点按 DFS 序从小到大排序。第二步，把排序后相邻关键点的 LCA 也加入节点集合。第三步，把整棵树的根节点也加进来，这一步是为了保证栈永远不会被弹空。第四步，整体重新按 DFS 序排序、去重，然后用单调栈搭边。

为什么一定要按 DFS 序排序？因为 DFS 序反映了一个节点在深度优先遍历中被访问的顺序，任意两个节点的 LCA 一定出现在这两个节点的 DFS 序之间。把相邻关键点的 LCA 收集上来，就不会漏掉任何必要的分叉点。而用栈建树的过程，本质是在维护一条“当前最右链”：每次处理一个新节点 u 时，如果栈顶节点不是 u 的祖先，说明栈顶属于另一条已经处理完的分支，可以弹掉；一直弹到栈顶是 u 的祖先为止，这个栈顶就是 u 在虚树上的父亲。

2.3 构建代码与两个容易写崩的细节

虚树构建的代码不长，但细节很多。先看核心部分：

int dfn[MAXN], siz[MAXN]; // DFS序与子树大小 bool isanc(int u, int v) { return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + siz[u]; } void build_virtual_tree(vector<int>& key) { sort(key.begin(), key.end(), [](int x, int y) { return dfn[x] < dfn[y]; }); key.erase(unique(key.begin(), key.end()), key.end()); vector<int> all = key; for (int i = 0; i + 1 < (int)key.size(); ++i) { all.push_back(get_lca(key[i], key[i + 1])); } all.push_back(1); // 根节点强制加入 sort(all.begin(), all.end(), [](int x, int y) { return dfn[x] < dfn[y]; }); all.erase(unique(all.begin(), all.end()), all.end()); for (int v : all) { vg[v].clear(); val[v] = 0; vt.push_back(v); // 记录本次用到的虚树节点 } vector<int> st; st.push_back(all[0]); // all[0] 一定是根 for (int i = 1; i < (int)all.size(); ++i) { int u = all[i]; while (!isanc(st.back(), u)) st.pop_back(); int p = st.back(); vg[p].push_back(u); vg[u].push_back(p); st.push_back(u); } }

第一个容易写崩的地方是祖先判断。有人图省事只写dfn[u] <= dfn[v]，这只能说明 u 先被访问，不能说明 u 是 v 的祖先。正确写法必须配合子树大小：dfn[u] <= dfn[v] && dfn[v] < dfn[u] + siz[u]。第二个容易写崩的地方是忘记把根加入 all。如果不加根，极端情况下栈会被弹空，然后访问st.back()直接越界。

3. DP转移的完整推导：血量如何在虚树上汇总

3.1 状态定义：把每次询问看成一次“输血”

在这道“血压游戏”里，我的理解是每个关键点有一份初始血量，血量要沿着树向上走，每经过一条边会消耗一点，最后汇总到某个根节点。定义val[x]表示节点 x 本轮自带的血量，只有关键点才有val[x] = a[x]，其它虚树节点val[x] = 0。再定义f(x)表示 x 的子树中所有血量向上传递，最终到达 x 时还剩下的总量。

转移其实很直接。先递归算出每个虚树儿子 v 的f(v)，然后这个血量要从 v 走到 u。原树上这两点的路径长度就是dep[v] - dep[u]，每走一步扣 1 点血，所以真正能到达 u 的贡献是max(0, f(v) - (dep[v] - dep[u]))。最终f(u) = val[u] + sum(贡献)。答案就是根节点 1 的f(1)。

3.2 长度折算：虚树边权到底怎么算

新手最容易在这里翻车：虚树压缩的是路径，但压缩掉的路径长度必须原样保留在边权里。原树每条边的权值是 1，但虚树上一条边 (u, v) 代表的是一条长度为dep[v] - dep[u]的原树链，所以边权不是 1，而是深度差。所有和长度挂钩的损耗，都要用这个差值去算。

不同的题目会有不同的折算方式，我列个常见的对应表：

“血压游戏”这种题的题眼，就是你怎么把血量从儿子节点传到父节点。只要把“路径上的损耗”正确折算到深度差上，DP 的核心就完成了。

3.3 两种常见转移模型以及顺序陷阱

我见过两类最常见的虚树 DP。第一类就是这种“汇总型”，所有子树的血量和贡献向上叠加，上面已经讲过。第二类是“极值型”或者“博弈型”，比如血量不是累加而是比较大小，或者双方轮流决策要取最大最小，这时候转移方程会变成f[u] = max(f[u], max(0, f[v] - dist))或者 minimax 的形式，但虚树的搭建完全一样。

这里有一个非常隐蔽的顺序陷阱：孩子到父节点的损耗，到底应该在合并前扣还是合并后扣？正确做法通常是先拿到孩子在子树的汇总值f[v]，然后单独扣除从 v 到 u 这段路径的损耗，再参与父节点的累加。因为每个孩子距离父节点的深度差不一样，如果你先把所有孩子的值加在一起再统一扣一次，就会多扣或者少扣，答案自然就错了。另外，LCA 节点不是关键点，它的val = 0，但你不能因为它没有血就跳过它，它是两条分支的汇合点，必须参与转移，否则两边贡献接不上。

4. 完整代码模板与关键细节解析

4.1 完整可跑的C++代码

把前面所有东西串起来，就是一个完整的模板。我用的是 C++17，LCA 用倍增，构建虚树用单调栈，DP 用递归：

#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 200005; const int LOG = 20; int n, q; vector<int> G[MAXN]; int dep[MAXN], dfn[MAXN], siz[MAXN], dfs_clock; int fa[MAXN][LOG]; ll a[MAXN], val[MAXN]; void dfs0(int u, int f) { dfn[u] = ++dfs_clock; siz[u] = 1; fa[u][0] = f; for (int i = 1; i < LOG; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1]; for (int v : G[u]) if (v != f) { dep[v] = dep[u] + 1; dfs0(v, u); siz[u] += siz[v]; } } int get_lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); int d = dep[u] - dep[v]; for (int i = 0; i < LOG; ++i) if (d >> i & 1) 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]; } bool isanc(int u, int v) { return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + siz[u]; } vector<int> vg[MAXN]; vector<int> vt; void build_vt(vector<int>& key) { sort(key.begin(), key.end(), [](int x, int y) { return dfn[x] < dfn[y]; }); key.erase(unique(key.begin(), key.end()), key.end()); vector<int> all = key; for (int i = 0; i + 1 < (int)key.size(); ++i) all.push_back(get_lca(key[i], key[i + 1])); all.push_back(1); sort(all.begin(), all.end(), [](int x, int y) { return dfn[x] < dfn[y]; }); all.erase(unique(all.begin(), all.end()), all.end()); vt.clear(); for (int v : all) { vg[v].clear(); val[v] = 0; vt.push_back(v); } vector<int> st; st.push_back(all[0]); for (int i = 1; i < (int)all.size(); ++i) { int u = all[i]; while (!isanc(st.back(), u)) st.pop_back(); int p = st.back(); vg[p].push_back(u); vg[u].push_back(p); st.push_back(u); } } ll dfs_dp(int u, int p) { ll sum = 0; for (int v : vg[u]) if (v != p) { ll got = dfs_dp(v, u); got -= dep[v] - dep[u]; if (got > 0) sum += got; } return sum + val[u]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfs0(1, 0); while (q--) { int k; cin >> k; vector<int> key(k); for (int i = 0; i < k; ++i) cin >> key[i]; build_vt(key); for (int x : key) val[x] = a[x]; cout << dfs_dp(1, 0) << '\n'; for (int x : key) val[x] = 0; } return 0; }

这套代码的核心逻辑很清晰：预处理原树的深度、DFS 序、倍增祖先，然后每轮询问构建虚树，给关键点临时赋初始血量，跑一遍虚树 DP，最后输出。如果你遇到的原题不是“关键点才有血量”，而是所有节点都有初始值，那只需要把for (int x : key) val[x] = a[x];这一句替换成在虚树构建时把整条链上的血量也折进去，思路完全相同。

4.2 复杂度与清空策略

预处理是 O(n log n)。每一个询问，排序关键点是 O(k log k)，求 LCA 是 O(k log n)，虚树节点数是 O(k)，DP 是 O(k)，所以单次询问是 O(k log n)，总复杂度 O(Σk log n)。只要 Σk 是 2e5 这种级别，跑起来毫无压力。

清空策略是虚树题最容易忽略的优化点。千万不要在每轮询问里去memset(val, 0, sizeof(val))，也不要memset(vg, 0, sizeof(vg))，那样等于把复杂度重新拖回 O(nq)。正确做法是像代码里那样，用一个vector<int> vt记录本轮虚树用到的节点，结束后只清理这些节点。如果你连 vector 遍历都不想写，也可以用时间戳技巧，给每个节点维护一个tag[u]，只有当tag[u] != 当前轮次时才清空，这样可以省掉一遍遍历，不过对这道题来说完全没必要。

4.3 多组数据下的初始化套路

再单独说一遍初始化，因为这里的坑很隐蔽。你在build_vt里把本轮所有虚树节点的val清零，然后在build_vt返回后再对关键点赋值val[x] = a[x]。这样上一轮残留的血量就不会串到这一轮里。如果你把赋值的顺序搞反了，比如主函数先赋值val[key[i]] = a[key[i]]，再调用build_vt，而build_vt内部又把val清了，那关键点的血量就直接丢掉了。

我见过不少选手卡在这里很久，表现是暴力对拍全对，一交上去 WA，调了半天发现是初始化顺序问题。所以这块我单独拎出来强调：先建虚树，清空本轮节点，再给关键点赋权，最后跑 DP。

5. 常见问题速查与避坑指南

5.1 构建期高频错误速查表

把平时容易被问爆的问题整理成一个表，方便直接对照排查。

5.2 DP期高频错误速查表

5.3 实战下来我保留的几点习惯

第一，先写一个朴素暴力，生成随机小数据对拍。虚树构建的边界太细了，什么栈空、LCA 重复、祖先判断错，光靠眼睛检查很难发现，对拍是最快的定位方式。第二，构建函数会对传入的关键点做排序和去重，如果后续还要用原始点集，记得先备份一份。第三，如果题目里的衰减规则不是“每步扣 1 点”，不要死记这个转移公式。我每次写之前都会在心里模拟一次血量从 v 到 u 到底经历了什么，损耗是按边数、按比例、还是按固定值，然后才写merge函数。

虚树这种东西，第一次接触会觉得构建过程很绕，但一旦你理解了“按 DFS 序排序 + LCA 补点 + 单调栈搭边”这三板斧，后续遇到的所有虚树题基本都是一条流水线：建树、清空、DP、输出。我自己现在遇到带“所有询问关键点总数有限”这种条件的树上题，第一反应就是往虚树上靠，这也是这道“血压游戏”给我留下的最大收获。