核心概述：莫队算法（含树上莫队）通过对查询重排为“近似旅行路径”，在相邻查询间仅增删端点元素以复用状态，实现离线解区间/树路径查询，复杂度约 O(N√Q)。
原文引述：
Description: Answer interval or tree path queries by finding an approximate TSP through the queries, and moving from one query to the next by adding/removing points at the ends. If values are on tree edges, change \texttt{step} to add/remove the edge and remove the initial \texttt{add} call (but keep \texttt{in}). Time: O(N \sqrt Q) Status: stress-tested
展开阐述：
- 定义与问题背景、适用场景
- 目标：批量处理区间或树路径查询，通过在查询间“就地移动”窗口/路径，减少每次从零开始的代价。
- 方法：对查询排序，使相邻查询“距离小”，仅需在两端 add/del 少量元素即可过渡到下一查询。
- 适用：各类可由端点增删维护的可交换、可逆的统计量（如不同元素个数、频率函数、贡献和等）。
- 接口职责与外部依赖
- 需由调用方实现：
- add(ind, end)：在左端(0)/右端(1)加入下标 ind 的元素；
- del(ind, end)：对应删除；
- calc()：在当前窗口/路径状态下返回答案。
- 需由调用方实现：
- 数组莫队（mo）的核心流程
- 分块：设块大小 blk ≈ N/√Q。
- 排序键：K([L,R)) = (L/blk, R ^ -( (L/blk) & 1 ))，即按块编号排序并对 R 采用蛇形顺序，降低回退幅度。
- 执行：
- 维护当前窗口 [curL, curR)，依排序依次移动到目标 [L,R)：
- while (curL > L) add(—curL, 0); while (curR < R) add(curR++, 1);
- while (curL < L) del(curL++, 0); while (curR > R) del(—curR, 1);
- 调用 calc() 记录答案。
- 维护当前窗口 [curL, curR)，依排序依次移动到目标 [L,R)：
- 树上莫队（moTree）
- 预处理：DFS 得到 I、L、R、par、in 等数组，以支持排序与祖先关系判定。
- 排序键：K([a,b]) = (I[a]/blk, I[b] ^ -( (I[a]/blk) & 1 ))。
- 路径迁移：
- 使用 step 宏在游走时对当前节点 c 进行“切换”（in[c] 取反，配合 add/del 与 end），两端逐步收敛至目标端点；
- 若权值在边上：依据原注释，将 step 改为对边 (a, c) 的增删，并移除初始 add（保留 in 标记）。
- 记录：通常在 end==1 时写入当前答案。
- 复杂度与边界条件
- 理论/经验复杂度约 O(N√Q) 或 O((N+Q)√Q)；树上版本同阶。
- add/del 必须可交换和可逆；否则在来回移动时答案无法一致维护。
- 选择合适 blk，可有效减少指针震荡；蛇形优化针对 R 指针的往返。
- 实现细节与坑
- 区间端点约定为半开 [L,R)；若使用闭区间需在迁移与 calc 中统一处理。
- 树上 in[] 与 step 一致性：保证每次切换不会重复计入或漏计。
- 边权版本的改动：严格按注释调整 step 与初始化流程。
- 变体/扩展
- 可与离散化、频次桶等结构结合，支持多种统计量。
- 对于在线/可更新数据，需改其他结构（如 012-数据结构-线段树）；对于前缀类计数亦可考虑 003-数据结构-树状数组。
- 正确性要点
- 通过排序将查询“近邻化”，再依靠 add/del 的可逆性和交换性保证不同访问顺序下状态一致，确保 calc 的正确输出。