括号序通过dfs遍历树，每个节点在进入和离开时各记录一次，形成长度为2n的序列，子树对应区间[in[u], out[u]]，路径查询需结合lca并处理奇数次出现节点。
括号序怎么把树变成序列
树上莫队的核心思路是把树结构压平成一维序列，这样就能复用普通莫队的分块和排序逻辑。括号序（Euler Tour Technique，ETT）是最常用的方法之一：对树做一次 DFS，每个节点在进入时记录一次，在离开时再记录一次，形成长度为 2 * n 的序列。
关键点在于：任意子树对应括号序中一段连续区间——但不是简单的一段，而是「首进 + 中间所有进出对 + 末出」，即节点 u 的子树对应区间 [in[u], out[u]]，其中 in[u] 是首次访问时间戳，out[u] 是最后一次（回溯前）时间戳。
注意：这个序列里每个节点出现两次，且中间夹着它的整个子树。所以单点查询或子树查询能转，但路径查询不能直接套用——得另想办法。
树上路径查询为什么不能直接用 [in[u], in[v]]
路径 u → v 在括号序里不是连续区间。比如 u 和 v 不在祖孙关系中，它们的 in 值可能分散在序列两端；即使 u 是 v 祖先，[in[u], in[v]] 会漏掉 v 到 u 路径上某些分支的「出点」，也会多包进无关子树。
正确做法是引入 LCA，并构造一个「路径对应的括号序覆盖集」：
- 设
l = in[u], r = in[v]，保证l ≤ r - 若
l和r对应节点有祖孙关系（即in[u] ≤ in[v] ≤ out[u]），则路径对应序列为[l, r]中只出现奇数次的节点（进为 +1，出为 −1，路径上节点恰好被覆盖一次） - 否则，设
w = lca(u, v)，路径对应序列为[out[u], in[v]] ∪ {in[w]}—— 这个并集在括号序里是两段连续区间加一个点，需特殊处理
实际实现中，通常用「异或标记」或「频次数组 + 奇偶翻转」来模拟「只统计出现奇数次的节点」，避免重建区间。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
Mo 排序时块大小为什么还是 sqrt(2 * n)
括号序长度是 2 * n，不是 n，所以分块大小必须按新长度算。用 sqrt(n) 会导致块数过多、排序开销上升，复杂度退化到 O(n√n) 甚至更差。
另外，每个查询在括号序中可能对应 1 段或 2 段区间（路径情形），需要统一拆成标准形式：
- 子树查询 → 单区间
[in[u], out[u]] - 路径查询 → 转为
[out[u], in[v]]（假设in[u] 且无祖孙关系）再补上 <code>in[lca]，然后用一个布尔标志位标记是否含额外点
排序函数里比较的是左端点所在块，右端点按奇偶块交替排序（即「奇偶优化」），这对 2n 长度依然有效，能减少右指针抖动。
实现时最易错的三个细节
括号序本身不难写，但树上莫队真正卡住人的地方往往在细节：
-
in[]和out[]时间戳必须从 1 开始（或全用 0-indexed），否则和莫队下标越界检查冲突 - LCA 必须用倍增或树链剖分预处理好，不能每次查询现场算，否则总复杂度爆炸；且
lca(u,v)的结果要确保在括号序中有对应in[lca]值 - 更新节点状态时，不能简单「加/减 1」，而要根据当前节点在括号序中是
in还是out来决定「加入」或「删除」——常见错误是把out[u]当作独立节点处理，导致子树统计重复或遗漏
路径查询的奇偶判定逻辑最好封装成独立函数，反复调试；别指望靠手算几个小样例就覆盖所有祖孙/非祖孙+深度奇偶组合。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
