“血压游戏”这道题，我第一次看到编号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 构建流程并不复杂，但细节很碎
虚树构建的经典流程是这样的：
- 把本次询问的关键点按 dfn（dfs 序）排序；
- 强制把根节点 1 加入关键点列表，并去重；
- 用一个栈维护当前虚树的最右侧链；
- 依次插入每个关键点，插入时求它与栈顶的 LCA；
- 根据 LCA 和栈顶的深度关系弹栈、连边；
- 最后把栈中剩下的节点依次连边。
这里最核心的“最右侧链”思想是：由于节点按 dfn 排序，当前正在处理的关键点一定在之前所有节点的“右侧”，所以虚树的右链可以用栈保存。每次加入新节点时，只需要和栈顶节点求 LCA，然后把这个 LCA 和中间路径上的节点处理干净。
3.2 参考代码：一次询问的虚树构建
我习惯把虚树边存到一个临时的邻接表里，为了避免反复清空整个数组，用一个 used 数组记录本次用到了哪些节点。
vector<int> vg[N]; // 虚树邻接表 vector<int> 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(vector<int> 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()); vector<int> 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 和 3，2 下面挂 4，3 下面挂 5，关键点是 4、5。排序后大概为 1、4、5。
处理 5 时，栈顶是 4，LCA(4,5)=1。此时 dep[1] 小于 dep[4]，并且栈中至少有两个节点。while 循环里，会把栈中第二个节点与栈顶连边，直到栈顶的上一个节点深度小于等于 LCA。如果不单独判断“st.back() != l”，就会把 4 和 1 直接连上，但正确应该先连 4-2、2-1，或者按虚树结构把 LCA=1 处理好。所以那段 if (st.back() != l) 的判断非常关键，它保证了 LCA 节点被正确塞进栈中。
另一个容易踩的坑是：根节点 1 必须在虚树里。如果不强加入 1，最后一次询问中如果根节点不是关键点，也没有出现在任何 LCA 中，那虚树根可能不是 1，最后 DP 结果就无处汇总。我习惯在 key 列表里直接 push(1) 并 unique。
4. DP 设计：用“时间戳 + 血量”合并蝙蝠
4.1 每个节点需要维护什么
虚树建好之后，树上每个节点 u 不再是一个简单的 DP 值，因为同一只蝙蝠到达 u 的时间可能不同，不同时间的蝙蝠不会互相影响。
所以我用一个结构体来维护 u 的“蝙蝠集合”：
struct Bag { map<long 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 插入覆盖，k=2e5 时大约每次移动 18 次，map 操作 18 次，整体常数虽然大，但完全能接受。
5.2 容易 WA 的几个边界
第一个边界是根节点必须在虚树里。我见过不少人只把给定关键点排序建虚树，结果 DFS 到根时发现虚树根不是 1，导致答案统计不到。强制加入 1 是最省心的做法。
第二个边界是“同归于尽”的实现。同一时刻出现多只血量相同的蝙蝠，它们全部死亡，不能保留任何一只。这个逻辑一旦写成“相等时保留一个”，样例可能都能过，但遇到极限数据就会挂。
第三个边界是 long long。深度差和时间在链上可能达到 2e5 量级，血量如果也很大，相加或者偏移时可能超过 int 范围。所有时间相关变量、base、key、血量建议统一开 long long。
第四个边界是虚树边的方向。构建虚树时，如果邻接表是无向的，DFS 时一定要记录父节点，避免走回父亲。我之前因为虚树建好后直接按无向图 DFS，结果每个点被访问了两次，Bag 被重复合并，答案直接乱掉。
5.3 对拍与造数据技巧
虚树题不能只靠样例验证，我一般会写一个暴力模拟程序，和虚树 DP 对拍。
暴力做法很直接：对每次询问，把关键点按深度从大到小排序，然后模拟每一秒蝙蝠的移动。维护每个节点当前时刻到达的蝙蝠集合，按规则合并。由于数据规模小（比如 n≤50，m≤10），暴力跑得动，可以对拍验证。
造数据时，我会刻意覆盖几个形态：
- 一条链：测试时间偏移和 base 累积是否正确；
- 菊花图：测试多个子节点同时到达根节点的情况；
- 深度相同但 LCA 不同的关键点：测试同时间合并的激烈程度；
- 所有关键点都相同：测试去重逻辑。
这份对拍帮我找到了一个隐藏 bug：当关键点里包含根节点 1 时，isKey[1] 也要被标记，否则根节点自身产生的蝙蝠会漏掉。
6. 总结这道题留给我的几个实操习惯
写这道题最直接的心得是：虚树本身不难，难的是把 DP 的“状态”设计对。
这道题里，每个节点不是一个简单的 dp 值，而是一个按时间戳组织的集合。正因为不同时间到达的蝙蝠不会互相影响，所以 map 的 key 才可以用时间戳。而“整体时间偏移”用 base 懒标记实现，是合并时最优雅的处理手段。
如果以后再遇到类似的“多只怪物向根移动，同时到达才战斗”的题，我大概率会直接想到这套模型：虚树压缩 + 时间戳 map + 启发式合并。这个模型还可以迁移到一些求“最早到达根节点的时间”或者“每个节点的贡献区间”的树上问题上。
最后分享一个调代码时的经验：如果某个测试点答案偏大，多半是同一节点的元素被重复上抛了；如果答案偏小，通常是“同归于尽”写成了保留；如果答案全零，看看是不是根节点根本没进虚树。这三个症状覆盖了我这道题 90% 的调试时间。
