“血压游戏”这道题我第一次看到编号5278G时还以为是个模拟题读完题面才发现是个非常标准的“虚树 树形DP”题目——树上若干个关键节点每次询问给一个集合经过一轮一轮向上移动之后问你汇聚到根节点的最大血量是多少。整道题把所有知识点都埋在了“关键点集合查询”这几个字里适合练虚树建法和树上信息压缩也适合检验自己对LCA和DP合并顺序的理解。这篇文章想把完整的做题链路讲透从题意还原、朴素想法为什么超时到虚树构建的代码细节再到最后那套带“时间戳”的启发式合并DP以及我实际写代码时踩过的一堆坑。如果你正在学虚树或者刷树上DP刷得有点懵这篇应该能帮你把框架立起来。1. 题意还原与核心模型蝙蝠上树血量说话1.1 题面可以这样理解原题来自某高校第18届网络友谊赛题面描述得比较随意我按记忆中有效信息还原一下题目模型。有一棵以 1 为根的有根树节点数为 n每个节点 i 有一个正整数权值 a[i]。接下来有若干次询问每次询问给出一个关键点集合 S表示集合里的每个节点初始都会产生一只蝙蝠蝙蝠的血量就是该节点的权值 a[i]。然后每一秒所有尚未到达根节点的蝙蝠同时沿父边向上走一步。当同一秒有多只蝙蝠到达同一个节点时它们会打一场如果这些蝙蝠中血量最大值唯一则血量最大的那只活下来继续向上走其余死亡如果血量最大值不唯一则所有血量最大的蝙蝠同归于尽这个节点这一秒不留下任何蝙蝠血量较小的蝙蝠不参与同归于尽直接被秒杀。不同秒到达同一个节点的蝙蝠不会碰面所以互不影响。蝙蝠到达根节点 1 后就不动了根节点同样按上述规则处理同一秒到达的蝙蝠。最终定义根节点的“血压”为所有最终能活着到达根节点的蝙蝠中血量最大的那个值。1.2 把“时间”翻译成“深度差”这个模型里最关键的转化是一个关键点 x 出发的蝙蝠到达它的祖先 u 需要的时间是 depth[x] - depth[u]。原因是蝙蝠每一秒只能向上走一条边路径长度就是深度差。于是两只蝙蝠能否在某个祖先节点相遇本质上等价于它们到达这个祖先的绝对时间是否相同。对于同一棵原树如果两个关键点 x、y 的初始深度相同那么它们到达任意共同祖先的时间也相同所以它们会在路径相交处打起来。如果深度不同它们的“节奏”天然错开几乎没有机会在中间节点碰面。不过有了虚树之后我们不需要手动讨论这种深度关系直接在压缩后的树上按时间戳合并就行。1.3 最终答案为什么是“最大值”有些同学可能会纠结不同时刻到达根的蝙蝠不是会碰面吗题目规则里只有同一时刻到达同一节点才会战斗。根节点也是一样。所以第 2 秒到达根的一只蝙蝠和第 5 秒到达根的另一只蝙蝠并不会打架。它们各自到达后都停留在根上。根节点的血压取的是“所有到达根节点的存活蝙蝠血量的最大值”。这就像量血压时取最高压一样只要有一只更强的蝙蝠到达它就更新根节点的血压值。这个定义让 DP 的目标非常清晰我们只需要让每一时刻最多保留一个“该时刻的胜者”最后在根节点的集合里取生命值最大的一项即可。2. 为什么朴素做法必然超时关键点很多但树更大2.1 直接对整棵树做 DP 的问题如果不加任何优化一次询问的做法是把所有关键点的蝙蝠沿树向上走模拟每一步在中间节点做合并。这个过程的复杂度是 O(n) 甚至 O(n^2)取决于实现。更常见的朴素做法是每次询问以根 1 为起点 DFS 一遍整棵树在每个节点统计所有关键点子树的情况。单次询问 O(n) 看似还行但如果 n 是 2e5询问次数再多一点直接爆炸。题目里所有询问的关键点总数往往是被约束在 2e5 级别的可是树的规模也可能达到 2e5。如果每次询问都遍历整棵树那即使总关键点很小也会被 n 拖死。2.2 虚树的核心思路丢掉没用的节点虚树解决的核心问题是我们只关心关键点以及那些会让关键点信息发生“交汇”的节点。仔细想一下两个关键点的信息只有在它们的 LCA 处才可能第一次发生碰撞。某条链上如果只有其中一个关键点的信息经过没有其他分支那么这一整条链上的中间节点都是冗余的可以直接压缩成一条带权边。于是对于一次询问我们只需要保留所有关键点任意两个关键点的 LCA根节点 1因为最终答案要汇总到这里。这些节点数量至多是关键点数量的两倍左右构建成一棵新的小树再在这棵小树上做 DP单次询问就从 O(n) 变成了 O(k log n)其中 k 是这次询问的关键点个数。2.3 复杂度为什么能接受虚树构建需要的关键操作是排序和求 LCA排序 O(k log k)每个关键点入栈出栈一次期间求 O(k) 次 LCA单次 LCA 用倍增是 O(log n)所以一次询问的构建复杂度是 O(k log n)。DP 部分如果用 map 维护时间戳每个关键点产生的蝙蝠在启发式合并下最多移动 O(log k) 次所以 DP 总复杂度约 O(k log k log n)。这个量级在 n、k 都是 2e5 时是完全可以接受的。3. 虚树构建那些容易写错的细节3.1 构建流程并不复杂但细节很碎虚树构建的经典流程是这样的把本次询问的关键点按 dfndfs 序排序强制把根节点 1 加入关键点列表并去重用一个栈维护当前虚树的最右侧链依次插入每个关键点插入时求它与栈顶的 LCA根据 LCA 和栈顶的深度关系弹栈、连边最后把栈中剩下的节点依次连边。这里最核心的“最右侧链”思想是由于节点按 dfn 排序当前正在处理的关键点一定在之前所有节点的“右侧”所以虚树的右链可以用栈保存。每次加入新节点时只需要和栈顶节点求 LCA然后把这个 LCA 和中间路径上的节点处理干净。3.2 参考代码一次询问的虚树构建我习惯把虚树边存到一个临时的邻接表里为了避免反复清空整个数组用一个 used 数组记录本次用到了哪些节点。vectorint vg[N]; // 虚树邻接表 vectorint used; // 本次询问用过的节点 int dfn[N], dep[N]; // dfn为dfs序dep为深度 int fa[N][LOG]; // 倍增祖先 int lca(int u, int v) { if (dep[u] dep[v]) swap(u, v); for (int i LOG - 1; i 0; --i) if (dep[fa[u][i]] dep[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]; } void addVEdge(int u, int v) { vg[u].push_back(v); vg[v].push_back(u); used.push_back(u); used.push_back(v); } void buildVTree(vectorint key) { key.push_back(1); // 强制根节点 sort(key.begin(), key.end(), [](int a, int b) { return dfn[a] dfn[b]; }); key.erase(unique(key.begin(), key.end()), key.end()); vectorint st; st.push_back(key[0]); for (int i 1; i (int)key.size(); i) { int u key[i]; int l lca(u, st.back()); if (l st.back()) { st.push_back(u); continue; } while ((int)st.size() 2 dep[st[(int)st.size() - 2]] dep[l]) { addVEdge(st[(int)st.size() - 2], st.back()); st.pop_back(); } if (st.back() ! l) { addVEdge(l, st.back()); st.pop_back(); st.push_back(l); } st.push_back(u); } while ((int)st.size() 2) { addVEdge(st[(int)st.size() - 2], st.back()); st.pop_back(); } int rootOfVT st[0]; // 虚树根一般是1 }3.3 栈模拟过程与易错点举个具体例子。假设原树是一条链1 - 2 - 3 - 4深度分别为 0、1、2、3一次询问给的关键点是 2 和 4。排序后关键点顺序可能是 1、2、4。开始栈里是 1。处理 2 时LCA(2,1)1等于栈顶 1所以直接入栈。此时栈为 [1,2]。处理 4 时LCA(4,2)2等于栈顶 2同样直接入栈。最后把栈中剩余节点 4-2、2-1 依次连边即可。如果关键点是 3 和 4排序后是 1、3、4。处理 3 时LCA(3,1)1等于栈顶 1入栈。处理 4 时LCA(4,3)3等于栈顶 3入栈。最后栈里是 [1,3,4]连出两条边也正确。我实际写的时候最容易犯的错是当 LCA 的深度介于栈顶和栈中第二个节点之间时忘记把 LCA 作为一个新节点插进去。例如原树 1 有两个儿子 2 和 32 下面挂 43 下面挂 5关键点是 4、5。排序后大概为 1、4、5。处理 5 时栈顶是 4LCA(4,5)1。此时 dep[1] 小于 dep[4]并且栈中至少有两个节点。while 循环里会把栈中第二个节点与栈顶连边直到栈顶的上一个节点深度小于等于 LCA。如果不单独判断“st.back() ! l”就会把 4 和 1 直接连上但正确应该先连 4-2、2-1或者按虚树结构把 LCA1 处理好。所以那段 if (st.back() ! l) 的判断非常关键它保证了 LCA 节点被正确塞进栈中。另一个容易踩的坑是根节点 1 必须在虚树里。如果不强加入 1最后一次询问中如果根节点不是关键点也没有出现在任何 LCA 中那虚树根可能不是 1最后 DP 结果就无处汇总。我习惯在 key 列表里直接 push(1) 并 unique。4. DP 设计用“时间戳 血量”合并蝙蝠4.1 每个节点需要维护什么虚树建好之后树上每个节点 u 不再是一个简单的 DP 值因为同一只蝙蝠到达 u 的时间可能不同不同时间的蝙蝠不会互相影响。所以我用一个结构体来维护 u 的“蝙蝠集合”struct Bag { maplong long, long long mp; // key为相对时间value为该时刻存活蝙蝠血量 long long base 0; // 整体时间偏移 };每个元素表示在某个具体时刻有一只血量为 value 的蝙蝠到达当前节点。mp 的 key 是“相对时间”真实时间等于 key base。这样的好处是当整棵子树的蝙蝠需要统一向上移动 w 秒时不需要修改 map 里的每个 key只要让 base w 即可。同一时刻最多只会有一个元素因为如果同一时刻有多只蝙蝠到达它们会按规则战斗最终要么留下一个血量最大的要么全部同归于尽。4.2 插入一只蝙蝠到集合插入的核心逻辑是处理同一真实时间下的合并。void addToBag(Bag b, long long realT, long long hp) { long long key realT - b.base; auto it b.mp.find(key); if (it b.mp.end()) { b.mp[key] hp; return; } if (it-second hp) { // 原来的血量更大新蝙蝠死亡 return; } if (it-second hp) { // 新蝙蝠血量更大替换 it-second hp; return; } // 血量相同且都是最大同归于尽 b.mp.erase(it); }这段代码看着简单但“同归于尽”的处理是很多 WA 的根源。如果血量大者唯一保留如果不唯一则整个时刻都没有蝙蝠存活。这里不能只写成取 max否则相同血量时会错误地保留一只。4.3 子树向上传播整体加时间偏移假设当前虚树节点是 u它的一个儿子是 v原树上 depth[v] depth[u]。那么 v 子树里所有蝙蝠到达 v 后还需要再走 depth[v] - depth[u] 秒才能到 u。我们不需要修改 v 的 bag 里的每一个元素只需要bag[v].base dep[v] - dep[u];然后遍历 bag[v].mp把每个元素按“真实时间”插入到 u 的集合中。因为 base 已经抬升所以真实时间就是 key base。这里要注意的是遍历插入时不能一边遍历一边删除 src 的 map否则迭代器会失效。我通常是先遍历完最后再统一 mp.clear()。4.4 启发式合并让小集合整体搬家如果我们每次都把子节点的 bag 合并到父节点的 bag 中而父节点的 bag 可能很小、子节点的 bag 很大那么每次把大集合里的元素逐个插入小集合复杂度会退化。正确的做法是启发式合并总把元素数量少的集合并入元素数量多的集合。但这里有一个坑合并前两个 bag 的“基准时间”可能不同。子节点 bag 的元素需要先整体加 w父节点 bag 的元素已经是到父节点的时间基准不能再加 w。我最终采用的写法是让当前节点维护一个 cur bag它始终代表“已经到达 u 节点的集合”。每当遇到一个子节点 v如果 cur 为空直接把 v 的 bag 拿来当 cur并让 cur.base w如果 cur 不为空比较两个 bag 的 size如果 cur 比 v 的 bag 大就把 v 的 bag 整体加 w 后逐个插入 cur如果 v 的 bag 比 cur 大就把 cur 里的元素转换成“v 基准时间”后插入 v 的 bag然后把 v 的 bag 作为新的 cur再整体加 w。这样每个元素每次被合并时所在集合大小至少翻倍所以每个关键点产生的蝙蝠最多被移动 O(log k) 次总复杂度可控。Bag* dfsVT(int u, int fa) { Bag* cur new Bag(); for (int v : vg[u]) { if (v fa) continue; Bag* child dfsVT(v, u); int w dep[v] - dep[u]; if (cur-mp.empty()) { cur child; cur-base w; continue; } int szCur (int)cur-mp.size(); int szChild (int)child-mp.size(); if (szCur szChild) { child-base w; for (auto pr : child-mp) { long long realT pr.first child-base; addToBag(*cur, realT, pr.second); } child-mp.clear(); } else { // 把cur中的元素转换到child的基准时间再插入child for (auto pr : cur-mp) { long long realT pr.first cur-base; long long realTAtV realT - w; addToBag(*child, realTAtV, pr.second); } cur-mp.clear(); cur child; cur-base w; } } if (isKey[u]) { addToBag(*cur, 0, a[u]); } bagAtNode[u] cur; return cur; }这段代码是这道题的核心。我第一次写的时候直接在合并完后对 cur-base 整体加 w结果同一个节点的元素被重复加了多次答案全错。后来才意识到cur 一旦代表“到达 u 的集合”它的 base 已经是 u 基准后续合并其他子节点时不能再次整体加。4.5 最终答案汇总DFS 结束后bagAtNode[1] 就代表根节点能收集到的所有存活蝙蝠。直接遍历它的 mp取 value 的最大值即可。long long ans 0; for (auto pr : bagAtNode[1]-mp) { ans max(ans, pr.second); } printf(%lld\n, ans);如果根节点集合为空ans 保持 0正好对应没有人活到根的情况。5. 复杂度分析与正确性边界5.1 复杂度拆解一次询问总共涉及 k 个关键点。虚树节点数 O(k)构建需要排序和 LCA单次 O(k log n)。DP 部分map 操作单次 O(log k)每个元素在启发式合并下移动 O(log k) 次所以总复杂度约 O(k log k log n)。如果题目总关键点数是 m所有询问的复杂度就是 O((sum k) log n log k)可以稳定跑过 2e5 的数据。做这类题时我一般直接估算为每个关键点被 log k 次 map 插入覆盖k2e5 时大约每次移动 18 次map 操作 18 次整体常数虽然大但完全能接受。5.2 容易 WA 的几个边界第一个边界是根节点必须在虚树里。我见过不少人只把给定关键点排序建虚树结果 DFS 到根时发现虚树根不是 1导致答案统计不到。强制加入 1 是最省心的做法。第二个边界是“同归于尽”的实现。同一时刻出现多只血量相同的蝙蝠它们全部死亡不能保留任何一只。这个逻辑一旦写成“相等时保留一个”样例可能都能过但遇到极限数据就会挂。第三个边界是 long long。深度差和时间在链上可能达到 2e5 量级血量如果也很大相加或者偏移时可能超过 int 范围。所有时间相关变量、base、key、血量建议统一开 long long。第四个边界是虚树边的方向。构建虚树时如果邻接表是无向的DFS 时一定要记录父节点避免走回父亲。我之前因为虚树建好后直接按无向图 DFS结果每个点被访问了两次Bag 被重复合并答案直接乱掉。5.3 对拍与造数据技巧虚树题不能只靠样例验证我一般会写一个暴力模拟程序和虚树 DP 对拍。暴力做法很直接对每次询问把关键点按深度从大到小排序然后模拟每一秒蝙蝠的移动。维护每个节点当前时刻到达的蝙蝠集合按规则合并。由于数据规模小比如 n≤50m≤10暴力跑得动可以对拍验证。造数据时我会刻意覆盖几个形态一条链测试时间偏移和 base 累积是否正确菊花图测试多个子节点同时到达根节点的情况深度相同但 LCA 不同的关键点测试同时间合并的激烈程度所有关键点都相同测试去重逻辑。这份对拍帮我找到了一个隐藏 bug当关键点里包含根节点 1 时isKey[1] 也要被标记否则根节点自身产生的蝙蝠会漏掉。6. 总结这道题留给我的几个实操习惯写这道题最直接的心得是虚树本身不难难的是把 DP 的“状态”设计对。这道题里每个节点不是一个简单的 dp 值而是一个按时间戳组织的集合。正因为不同时间到达的蝙蝠不会互相影响所以 map 的 key 才可以用时间戳。而“整体时间偏移”用 base 懒标记实现是合并时最优雅的处理手段。如果以后再遇到类似的“多只怪物向根移动同时到达才战斗”的题我大概率会直接想到这套模型虚树压缩 时间戳 map 启发式合并。这个模型还可以迁移到一些求“最早到达根节点的时间”或者“每个节点的贡献区间”的树上问题上。最后分享一个调代码时的经验如果某个测试点答案偏大多半是同一节点的元素被重复上抛了如果答案偏小通常是“同归于尽”写成了保留如果答案全零看看是不是根节点根本没进虚树。这三个症状覆盖了我这道题 90% 的调试时间。