题目分析

1. 核心转化 题目要求计算 $\sum_{i=l}^{r} \mathrm{dep}[\mathrm{LCA}(i,z)]$。 我们需要理解 $\mathrm{dep}[\mathrm{LCA}(i, z)]$ 的几何意义：它等价于 根节点到 $i$ 的路径 与 根节点到 $z$ 的路径 的 交集包含的点数。

基于这个性质，问题可以转化为一个经典的树上操作模型：

1. 将树上所有点权初始化为 0。
2. 对于区间 $[l, r]$ 中的每一个点 $i$，将 根到 $i$ 的路径 上所有点的权值 $+1$。
3. 完成上述操作后，查询 根到 $z$ 的路径 上的点权之和。

2. 离线与差分 由于 $i$ 的范围是 $[l, r]$，直接做会导致重复操作。我们可以利用差分思想将区间查询转化为前缀查询：

$$\text{Ans}(l, r, z) = \text{Calc}(1, r, z) - \text{Calc}(1, l-1, z) $$

其中 $\text{Calc}(1, k, z)$ 表示：将 $1 \sim k$ 的路径加 1 后，查询 $z$ 的路径和。

这样，我们可以将所有询问离线处理：

1. 将所有询问拆解为两个操作：在时刻 $l-1$ 减去结果，在时刻 $r$ 加上结果。
2. 按照 $1 \sim n$ 的顺序扫描。当扫描到节点 $i$ 时：
   • 执行 路径修改：将 $1 \to i$ 路径上的点权 $+1$。
   • 处理所有挂在当前时刻 $i$ 的询问：执行 路径查询 $1 \to z$ 的和。

3. 数据结构选择 我们需要支持的操作是：

• 链加：$1 \to u$ 路径点权 $+1$。
• 链求和：查询 $1 \to u$ 路径点权和。

常规做法是使用 树链剖分 (HLD) 或 Link-Cut Tree (LCT) 配合线段树，时间复杂度为 $O(m \log^2 n)$ 或 $O(m \log n)$。 这份代码采用了一种更为高级且常数优秀的数据结构：全局平衡二叉树 (Global Biased Tree)，它本质上是对树链剖分的一种优化维护方式。

---

代码详解

1. 全局平衡二叉树 (GBT) 的构建

代码没有使用线段树维护重链，而是为每一条重链构建了一棵加权平衡二叉树。

• 权值定义：每个节点的权值设为 sum[u] - sum[hson[u]]，即该节点轻子树的大小。
• 建树 (dfs2, build)：
  • dfs2 遍历整棵树，对于每条重链，收集链上节点。
  • build 函数类似于构建 Huffman 树或线段树，它递归地寻找一个分割点 p，使得左右两部分的权值和尽可能接近。这样构建出来的二叉树高度是 $O(\log n)$ 的。
  • 树中的节点 T[k] 维护了：
    • lc, rc: 左右孩子（分别对应重链上深度较浅和较深的部分）。
    • fa: 父节点（如果是重链根节点的父节点，则指向树上的父节点，即虚边）。
    • sum, val, lz: 分别维护子树和、节点值、懒标记。

2. 路径修改 (Achain)

对应操作：根到 $k$ 路径权值 $+1$。 类似于 LCT 的 Access 操作，自底向上跳：

• 如果当前节点 $k$ 是其父节点的重儿子（在 BST 中体现为右孩子或左孩子），我们需要根据相对位置判断是否要覆盖 BST 的左子树（即重链上深度更浅的部分）。
• tp 变量用于标记当前节点是否属于上一级节点的“左侧”路径（深度更浅的方向）。
• 通过 lz 标记实现区间更新，通过 val 更新单点。

3. 路径查询 (Qchain)

对应操作：查询根到 $k$ 路径权值和。 同样自底向上跳：

• 维护变量 res (累加和) 和 cs (当前路径在当前子树中覆盖的节点数)。
• 当从 BST 的右子树（深度深）跳向父节点时，说明父节点及其左子树（深度浅）都在路径上，需要累加 T[T[k].lc].sum 和 T[k].val。
• 同时，沿途遇到的懒标记 lz 根据覆盖的节点数 cs 贡献到结果中。

4. 主程序流程

1. 输入与建图：读入树结构和询问。
2. 询问离线：将每个询问 $(l, r, z)$ 拆分为两个操作：
   • 在 $L[i]-1$ 处记录 tod，标记为负（减）。
   • 在 $R[i]$ 处记录 tod，标记为正（加）。
3. 预处理：dfs1 求重儿子，dfs2 构建全局平衡二叉树。
4. 扫描处理：
   • 循环 i 从 $1$ 到 $n$。
   • 调用 Achain(i) 修改路径。
   • 遍历 tod[i] 中的询问，调用 Qchain(tar[id]) 更新答案。
5. 输出：注意取模 201314。

---

复杂度分析

• 时间复杂度：
  • 预处理构建 GBT：$O(n)$。
  • 每次修改和查询：由于 GBT 的平衡性质，树高严格控制在 $O(\log n)$，单次操作复杂度为 $O(\log n)$。
  • 总时间复杂度：$O((n + q) \log n)$。
• 空间复杂度：
  • 存储树结构和 GBT 节点，为 $O(n)$。

总结

这份代码使用了离线差分将问题转化为动态路径加和路径求和，并利用全局平衡二叉树这一高效数据结构来实现 $O(\log n)$ 的树上路径操作，是解决此类 LNOI/CTSC 级别树上统计问题的优秀模板。