牛客 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会挂直接算一下就能感受到差距。假设 n1e5q1e5每次询问给 k 个关键点且 Σk2e5。朴素做法是一次询问做一次完整树上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(vectorint key) { sort(key.begin(), key.end(), [](int x, int y) { return dfn[x] dfn[y]; }); key.erase(unique(key.begin(), key.end()), key.end()); vectorint 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); // 记录本次用到的虚树节点 } vectorint 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而是深度差。所有和长度挂钩的损耗都要用这个差值去算。不同的题目会有不同的折算方式我列个常见的对应表损耗模型子节点返回贡献的计算方式每步扣 1 点max(0, f[v] - (dep[v] - dep[u]))每步按比例衰减f[v] * pow(rate, dep[v] - dep[u])固定代价通过max(0, f[v] - cost * (dep[v] - dep[u]))求路径上最大值在虚树边上额外维护最大值信息“血压游戏”这种题的题眼就是你怎么把血量从儿子节点传到父节点。只要把“路径上的损耗”正确折算到深度差上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代码把前面所有东西串起来就是一个完整的模板。我用的是 C17LCA 用倍增构建虚树用单调栈DP 用递归#include bits/stdc.h using namespace std; using ll long long; const int MAXN 200005; const int LOG 20; int n, q; vectorint 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]; } vectorint vg[MAXN]; vectorint vt; void build_vt(vectorint key) { sort(key.begin(), key.end(), [](int x, int y) { return dfn[x] dfn[y]; }); key.erase(unique(key.begin(), key.end()), key.end()); vectorint 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); } vectorint 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; vectorint 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)。正确做法是像代码里那样用一个vectorint 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 构建期高频错误速查表把平时容易被问爆的问题整理成一个表方便直接对照排查。错误现象原因解决办法栈底节点为空或越界没有把根节点加入 all或祖先判断写错强制all.push_back(1)用dfn siz判断祖先虚树里多出大量无关节点只加入关键点忘了相邻关键点的 LCA排序后对相邻点get_lca并加入同一个节点被连了多条重复边关键点没去重排序后uniqueLCA 加入后再统一unique边连得乱七八糟父子关系错乱排序用了深度而不是 DFS 序必须按dfn[x]排序答案少了根方向的一整段构建时没有把根当作虚树起点加入根节点DP 从根开始递归5.2 DP期高频错误速查表错误现象原因解决办法贡献算出负数没做max(0, x)截断每个孩子贡献单独if (got 0)答案比预期大或小先合并再统一扣距离每个孩子先扣距离再累加递归栈溢出虚树深度可能接近 k改成迭代栈 DFS 或增大递归栈限制上一轮血量串到本轮val没清干净用vt记录节点并清空或加时间戳非关键点血量被误算把原树所有节点都当关键点赋了值只在key集合里赋val5.3 实战下来我保留的几点习惯第一先写一个朴素暴力生成随机小数据对拍。虚树构建的边界太细了什么栈空、LCA 重复、祖先判断错光靠眼睛检查很难发现对拍是最快的定位方式。第二构建函数会对传入的关键点做排序和去重如果后续还要用原始点集记得先备份一份。第三如果题目里的衰减规则不是“每步扣 1 点”不要死记这个转移公式。我每次写之前都会在心里模拟一次血量从 v 到 u 到底经历了什么损耗是按边数、按比例、还是按固定值然后才写merge函数。虚树这种东西第一次接触会觉得构建过程很绕但一旦你理解了“按 DFS 序排序 LCA 补点 单调栈搭边”这三板斧后续遇到的所有虚树题基本都是一条流水线建树、清空、DP、输出。我自己现在遇到带“所有询问关键点总数有限”这种条件的树上题第一反应就是往虚树上靠这也是这道“血压游戏”给我留下的最大收获。