第一次看到这场训练的G题时我心里其实有点犯嘀咕。倒不是说题目本身长得吓人而是它的出题风格和通常的“压轴题套路”不太一样没有一上来就给你一棵满二叉树的树剖也没有花里胡哨的卷积形式就是一棵很朴素的树配上一个很直接的询问。但恰恰是这种“朴素”最容易让人在推正解的时候产生“好像会了”的错觉然后在代码里翻车。这次训练我花了大概一个半小时在这道题上把暴力和正解都写了一遍过程中踩了几个值得记录的坑也把思路重新梳理了一遍趁热分享出来。1. 这道题到底在问什么先把题意压缩到最简G题的题干虽然写了一大段故事背景但剥掉包装之后核心诉求其实很干净。我这里用自己的话重新描述一遍方便后面聊思路时不跑偏。题目给了一棵n个节点的树节点从1到n编号每个节点上有一个整数权值a_i。接下来有q次询问每次询问给出一个起点u和一个非负整数k要求你找出从u出发沿着树上的简单路径向上走也就是朝根的方向走恰好k步后到达的节点v然后输出以v为根的子树中所有节点权值的某种聚合值。聚合方式题目里已经定义好了这里不展开细节你只需要知道它满足“可合并”的性质也就是说我们需要一种方式把一棵子树的信息快速拼出来。需要特别注意的是这棵树的根是固定的所以“向上走”的方向没有任何歧义u的k级祖先一定是唯一的。如果u的深度小于k那这次询问就属于非法情况题目会要求你输出一个约定好的空值。我第一次读完题后的第一反应是这不就是“倍增求祖先 子树查询”的缝合怪吗预处理出每个节点的2^j级祖先然后对于每个询问先倍增跳到目标节点再用 DFS 序把子树转成区间最后套一个线段树或者树状数组就能做。这个思路本身没有任何问题也是这题最直观的暴力解法。但如果只是这么写这道题放在第三题都嫌简单它能在 G 题的位置上肯定有它的讲究。真正的难点藏在数据范围里。题目没有给出特别宽松的约束n和q的上限都在2 × 10^5级别而且每个节点的权值范围很大聚合操作还涉及顺序问题不能简单地把两个子树的结果直接合并了事。你如果天真地认为“树状数组维护一下前缀和就行”那只能说明还没有看清楚聚合操作对顺序的依赖。这一点后面细说。2. 为什么不能直接倍增加树状数组聚合操作的顺序依赖很多人包括我一开始看到“向上走 k 步到达 v然后查子树”就会下意识地开始写倍增和树状数组。但在动手之前我多花了两分钟去想聚合操作本身结果发现事情没那么简单。假设题目要求的聚合操作是求子树内所有点权的最大值那确实无脑DFS 序加树状数组就是标准答案。但如果操作是“把子树内所有点权按某种顺序排成一个序列然后做前缀异或”或者“维护一个有限状态自动机的转移”这类带顺序的东西那么子树查询的关键就不只是“有哪些节点”还包括“这些节点的访问顺序”。G 题这次就给我挖了这么一个坑它要求的聚合结果和子树在 DFS 序中的区间位置是对应的但因为操作不满足交换律你不能简单地用两个前缀相减得到区间答案。这直接让“倍增求祖先 区间查询”的常规组合失去了意义。我看了不少人的赛后代码发现他们大多都用了某种支持“动态合并子树信息”的数据结构而不是常规的静态区间查询原因就在这。换句话说这道题真正考察的点是你能否按照题目要求的聚合方式把一棵子树的完整信息维护出来并在多次询问中快速响应。由于每个查询的v是变化的你不能只做一次全局预处理就万事大吉必须在查询时动态地拼出答案。我当时重新读了三遍题目才确认了聚合操作的不可交换性。确认完之后原本想好的做法全部推翻重新从暴力开始推。3. 暴力的正确姿势先保证小数据不出错在推正解之前我把暴力做法写得很保守确保小数据能对。暴力的逻辑非常简单对于每个询问(u, k)先循环k次、每次取u fa[u]如果中途发现u已经变成0表示不存在的父节点就直接返回空值。找到v之后再对以v为根的子树做一次 DFS按题目要求的顺序收集信息并计算聚合结果。代码量大约五十行思路零技术含量但它有非常大的价值它是验证后续所有优化做法正确性的唯一标准。这里我给自己定了一个规矩——任何优化做法都必须先通过和暴力对拍的方式验证而不是靠“我推了一下应该没问题”这种盲目自信。在写暴力的过程中有几个细节值得注意k的取值可能很大但暴力循环不会超时吗不用担心因为我只在小数据上跑n和q都限制在10^3以内暴力是能轻松跑完的。向上跳的过程中父节点数组的边界处理一定要是“深度不够就返回空值”不能想当然地用fa[u][j] 0来判断因为0这个节点在邻接表里可能被当成合法节点存过。聚合操作如果是不可交换的那么收集子树信息时必须严格按照子树内节点的某种顺序来遍历比如 dfs 序的先后顺序否则结果会出错。暴力跑通之后我拿着几组手造数据反复确认了输出才放心开始推正解。这一步浪费不了多少时间却能让你在后面对拍时节省大量时间。4. 正解心路从重链剖分想到重构树4.1 第一步借助树上倍增定位祖先节点定位u的k级祖先是一个经典问题了用倍增数组up[u][j]可以在O(log n)的时间内完成。做法是预处理时对每个节点u令up[u][0]等于它的父节点然后up[u][j] up[up[u][j-1]][j-1]。查询的时候把k拆成二进制位逐位往上跳。这个部分属于基础但需要留意的是如果你的题目中根节点的父节点设置成0那么up[root][j]也全部是0在查询时要注意判断v ! 0否则后续访问子树会出错。4.2 第二步子树信息动态合并的两种路线定位到v之后剩下来的问题就变成如何快速获取v的子树聚合值。这里有两种主流路线分别适合不同的情况。路线一平衡树/线段树维护 DFS 序区间。如果你能保证聚合操作满足交换律那么直接对 DFS 序建一棵线段树每个节点维护区间内所有节点的聚合值查询时覆盖对应的区间即可。但 G 题不满足交换律所以我们需要一个能严格按 DFS 序从左到右合并的区间查询结构。其实线段树是能做到这一点的只要在build和query时严格按照左儿子到右儿子的顺序合并即可。因为线段树天然按区间划分query 时按左到右的区间顺序合并。也就是说即便聚合操作不可交换只要它满足结合律线段树还是能做区间查询。那问题来了为什么不能直接上线段树G 题的坑在于v会随着查询变化而每次查询的v是某棵子树在 DFS 序上对应的是一段连续的区间。理论上线段树查询区间[dfn[v], dfn[v] size[v] - 1]是完全可行的。所以这条路其实没断我之前说不行是我一开始想用树状数组“前缀相减”导致的错误想法。线段树本身并没有受限。但如果题目操作是“按 DFS 序顺序合并”的线段树依然可以在O(log n)时间内完成查询。于是我在这一步重新审视G 题是不是真的需要更复杂的数据结构答案是不一定。路线二如果每个询问的 k 固定可以利用树上启发式合并预处理。假设所有询问的k都相同那我们可以一次 DFS 求出所有节点的k级祖先然后对每个节点保存一个子树 DFS 序区间最后一次性把所有询问离线处理用莫队或者常规区间数据结构跑完。但 G 题的k是每个询问不同的所以不能直接用这个思路。也就是说线段树的做法其实已经足够应对这题的大部分情况了。真正让我多花时间的是题目中可能存在的另一个隐含条件——询问的k是否保证合法以及聚合操作的复杂度是否足够小如果聚合两个结果的时间是O(m)其中m是信息大小那么线段树合并两个节点信息时总复杂度就会从O(log n)变成O(m log n)这时就需要考虑信息量的大小了。4.3 第三步关于信息合并复杂度的思考我在写到这步时特意回去看了眼题目的输出要求每个节点权值可能很大而聚合结果的数据量远远小于子树大小。也就是说合并两个聚合结果时并不是要你把两个集合完整地拼起来而是把两个已经压缩过的信息做一次“叠加”。如果这个叠加操作的代价是常数级那么线段树查询就是O(log n)的。但如果叠加操作的代价是O(size_of_info)而且这个size_of_info可能达到O(n)那问题就会变得非常棘手。因为每条链上的信息都要一路向上汇总总复杂度可能退化到O(n^2)。所以判断一道题能不能用“子树区间查询 线段树”来解决核心就看两步聚合操作是否具有结合律合并两个聚合信息的复杂度是否足够小把这个想清楚之后我就不再纠结要不要写更复杂的数据结构了。G 题最终需要的是线段树最多加上一点线段树动态开点或者离散化的细节。至于有些人可能提到的 “Link-Cut Tree” 或者 “树上启发式合并”在2×10^5的数据范围下都不是必要的。5. 线段树处理的几个分量顺序、边界的调试实录5.1 数据组织DFS 序是唯一的分组依据线段树方案的第一步是把树的 DFS 序求出来。这里的 DFS 序我指的是“访问节点的顺序”也就是dfn[u] timer那种。然后对每个节点u维护sz[u]表示子树大小。这样以v为根的子树就映射到区间[dfn[v], dfn[v] sz[v] - 1]。在写 DFS 序的时候有一个细节必须注意如果你用的是递归 DFS那么对于n 2×10^5的树递归深度可能会爆栈。我一开始没想太多直接写了递归结果在测试时拍出了栈溢出。解决办法有两个一是把树改成用栈的迭代 DFS二是把递归的栈空间通过编译器选项调大。个人推荐用迭代写法更保险也方便在 DFS 过程中同时处理up数组和sz。5.2 线段树维护不可交换聚合的关键写法既然聚合不可交换pushUp 时就要严格按照“左儿子结果 右儿子结果”的顺序做聚合不能因为懒就写成merge(val[ls], val[rs])或merge(val[rs], val[ls])然后不管了。看起来是小事但对某些数据会直接导致结果错误。在我写的模板里我把聚合操作封装成一个函数Node merge(Node L, Node R) { // 按题目要求的顺序合并 L 和 R Node ret; ret.val cal(L.val, R.val); return ret; }然后线段树的pushUp固定写成tr[p] merge(tr[p 1], tr[p 1 | 1]);这样保证每个内部节点存储的都是“该区间从左到右依次计算后的聚合值”。查询的时候我采用了一个经典的小技巧用一个bool标记表示当前是否已经收集过左半部分的信息然后用一个变量res作为累积结果。Node query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return tr[p]; int mid (l r) 1; if (qr mid) return query(p 1, l, mid, ql, qr); if (ql mid) return query(p 1 | 1, mid 1, r, ql, qr); Node left query(p 1, l, mid, ql, qr); Node right query(p 1 | 1, mid 1, r, ql, qr); return merge(left, right); }这个写法能保证查询区间被拆分成若干段时严格按照从左到右的顺序合并不会因为递归顺序导致区间顺序错乱。5.3 倍增与线段树联调时遇到的隐蔽错误我在调试时遇到一个很隐蔽的 bug值得拿出来单独说说。一开始我预处理倍增数组时把up[u][0]写成fa[u]而fa[u]是在建树时通过父节点传入的。这个逻辑本身没有错但我忽略了根节点的父节点是0而0在邻接表数组中会被当做一个合法节点。于是当我查询一个深度不足k的询问时倍增会把u跳到0然后我又拿着dfn[0]和sz[0]去线段树里查得到的是一个完全错误的结果。调试的时候我发现对于“深度不够”的询问答案应该是约定的空值但程序总是输出一个奇怪的数字。加上一行判断if (u 0) return empty;之后问题立刻消失。所以这里想提醒大家倍增求祖先和线段树查询的边界判断一定要独立清晰不能互相依赖。先判断合法性再跳倍增再进入数据结构三步分开写不要在图省事的情况下把它们揉在一起。6. 另一种思路树上启发式合并能否更省事在把线段树方案写完并通过随机数据对拍之后我仍然不死心地想了想这道题还有没有其他解法。毕竟 G 题放在第六题之后单纯考“倍增 线段树”虽然合理但未免有点太常规。结果我发现如果你愿意牺牲一些常数用 DSU on tree树上启发式合并也可以做而且代码写起来更直观。具体思路是我们需要回答若干询问每个询问是“u的k级祖先v的子树聚合值”。如果我们能一次性算出每个节点的子树聚合值那对于任何询问只需要先倍增找到v然后直接查表就行。问题又回到“如何高效求出所有节点的子树聚合值”。对于一棵树我们可以用 DSU on tree 在O(n log n)的时间内把每个节点的子树信息维护出来前提是信息的插入和删除操作都能在O(1)或O(log n)内完成。因为 DSU on tree 的核心思维是轻重儿子分治每次保留重儿子的信息暴力把轻儿子的信息合并上来。对于不可交换的聚合操作DSU on tree 有一个天然劣势它无法保证“子树内所有节点按正确的顺序插入”。因为你合并轻儿子时遍历的顺序和 DFS 序不一定一致。如果聚合操作又不可交换那 DSU on tree 的做法就很难保证正确性。除非你能在将信息插入集合时额外带上“谁是左、谁是右”的信息否则很容易出错。所以我的结论是对于 G 题这种不可交换聚合操作线段树维护 DFS 序区间才是标准且稳妥的正解。DSU on tree 虽然能做部分可交换的题但在这里性价比极低。我写了一份 DSU on tree 的草稿代码运行结果确实有一半的随机数据能过但偶尔会挂查了几次发现都是顺序问题。这个方向我最终放弃了不过把这个思路写出来是想提醒大家选算法不能只看复杂度必须结合操作的性质。7. 对拍方案设计我如何确保代码真的正确一道数据结构和树的综合题写出思路不等于写对代码。为了确保我的2×10^5数据下不超时、答案正确我做了三件事分别是构造数据、对拍脚本、以及特殊边界测试。7.1 构造数据的几个关键类型链状树每个节点只有一个孩子深度达到n。这种数据会极大程度考验倍增的极限情况也会让线段树的查询全部集中在一条链的尾部区间。星形树根节点下面挂着所有其他节点深度很小。这样测的是在极浅深度下倍增和区间查询是否正常。随机树随机生成父节点fa[i] rand() % (i - 1) 1保证是一棵有根树节点分布均匀。蒲公英型随机树随机生成层数和度数让某些子树特别大、某些子树特别小模拟不均衡的 DFS 序区间分布。每次生成完树之后再随机生成若干组询问(u, k)。其中我刻意把k设置为三种情况合法且较小比如k 0, 1, 2合法且较大比如k depth(u) - 1非法k depth(u)。这样可以保证边界条件被充分覆盖。7.2 对拍脚本与数据生成代码对拍流程很传统写一个暴力程序brute.cpp写一个优化程序solve.cpp再写一个数据生成器gen.py用 shell 脚本循环跑即可。这里分享一个我常用的最小化对拍脚本#!/bin/bash for i in $(seq 1 1000); do python3 gen.py input.txt ./brute input.txt ans_brute.txt ./solve input.txt ans_solve.txt if diff -bq ans_brute.txt ans_solve.txt /dev/null; then echo Test $i: OK else echo Test $i: WA break fi done这里有个小建议不要用diff直接比较带有空格差异的文件最好在输出时统一用\n分隔并且每行结尾不要有多余空格。我遇到过好几次因为多打了一个空格导致对拍误报 WA 的情况浪费了不少时间后来干脆在输出函数里做严格处理。7.3 针对链接关系和深度的边界测试边界测试我单独写了三个 casen 1只有一个根节点。此时sz[root] 1所有询问k只要大于0就是非法的必须输出空值。这个 case 虽然简单但很多人会在初始化dfn时漏掉sz数组的发生。q 1树的形态完全随机。验证单次询问是否在log n时间内出结果。所有询问的k都等于0。这时候每个询问的答案就是u自身的权值相当于在测试线段树的单点查询功能。这些边界 case 全部通过之后再回头处理大数据的压力测试看看是否超时。一分钟出结果基本就算合格。8. 性能复盘复杂度与常数优化记录8.1 明确的总复杂度最终方案的时间复杂度是预处理O(n log n)单次询问O(log n)总复杂度O((n q) log n)空间复杂度大约O(n log n)用来存倍增数组加上O(n)的线段树。如果内存比较紧倍增数组可以换成“树上离线求 k 级祖先”的方式用vector在 DFS 时动态维护祖先链这样空间能压到O(n)。但实现起来需要分步骤处理询问不如在线做法那么直观。我在比赛中直接用倍增n是2×10^5log n约为18up数组需要的空间是n * 19 * 4字节约15MB完全在内存限制之内。8.2 常数优化从递归到迭代线段树的查询如果用递归常数略大但问题不大。不过我在写 DFS 序时递归爆栈的问题前面已经提过所以这里强调树的 DFS 序求解请直接用迭代栈。一个简单的迭代 DFS 写法是void dfs(int root) { vectorint stk; stk.push_back(root); while (!stk.empty()) { int u stk.back(); stk.pop_back(); dfn[u] timer; if (u ! root) { // 处理父节点已经记录过的事 } for (int v : g[u]) { if (v fa[u]) continue; fa[v] u; stk.push_back(v); } } }但这里有个坑如果你在 DFS 过程中直接计算sz上面的栈式写法就不太好处理“先访问子节点再回传子树大小”的逻辑。需要改用记录进入和离开状态的两趟式栈void dfs_iter(int root) { vectorpairint, int stk; // {node, state} stk.push_back({root, 0}); while (!stk.empty()) { auto [u, state] stk.back(); stk.pop_back(); if (state 0) { dfn[u] timer; stk.push_back({u, 1}); for (int v : g[u]) { if (v fa[u]) continue; fa[v] u; up[v][0] u; stk.push_back({v, 0}); } } else { sz[u] 1; for (int v : g[u]) { if (v fa[u]) continue; sz[u] sz[v]; } } } }这比递归版本多写几行但换来了稳健性和可调试性个人觉得值。8.3 线段树的建树与查询心得体会建树时我把每个dfn位置上的权值先放到一个数组base[dfn[u]] a[u]然后用标准线段树建树这样所有区间查询都不需要关注节点本身的信息只管dfn区间。这样分离数据组织和逻辑组织思路清晰很多。查询部分如果发现ql和qr都已经覆盖到了就直接返回节点值否则递归左右儿子。由于聚合不可交换如果同时需要访问左右儿子一定要注意先查左再查右合并时也不能反过来。9. 复盘收获哪些经验和失误值得记住这道 G 题做完给我最大的几个感受可以总结成下面几条适合任何一次训练后回看。遇到“树上第 k 级祖先 子树查询”这样的组合题优先想倍增 区间数据结构但这只是框架。真正的难点在于聚合操作是否满足交换律这直接决定了你能不能用差分或前缀和的思路。如果不可交换必须老老实实用支持区间合并的数据结构。暴力的价值被严重低估。我这次如果没有先写暴力对拍直接上线段树大概率会死在一个不起眼的边界判断上浪费至少半小时。有暴力程序做对照优化就能变得非常笃定。DFS 序不是“求一遍就万事大吉”的。你必须保证dfn、sz、base数组三者的对应关系严格一致任何一步出错都会导致后续查询整体漂移。调试时建议把树打印出来看每个节点的dfn和sz是否符合直觉。善用对拍脚本但也要给对拍脚本加“边界测试”功能。只随机生成数据会漏掉很多非法询问和极端树形。写代码前先手算几组数据的期望答案。这能让你对题目本身的理解更加扎实而不是边写边猜。实际比赛中我在暴力程序上花了大约 15 分钟然后再花了 30 分钟实现了线段树和倍增再用 30 分钟进行随机数据对拍和边界调整整个过程算是有条不紊。如果一上来就想着写正解反而可能因为缺少参照而陷入逻辑死角。如果有机会做同一道题的赛后复盘我的建议是把暴力和正解放在两个文件里保留对拍脚本然后对着数据一步步看结果。你会发现很多原本觉得“玄学”的问题其实都是数组下标或者顺序细节造成的。不要怕花时间在暴力上也不要怕推翻已经写了一半的正解。算法竞赛里最贵的不是时间而是方向上一直错下去而不自知。