# 祖先子树的分层统计：路径加与路径求和

[alternative.cpp](alternative.cpp) 使用重链剖分和两个树状数组，以 $O(n)$ 空间支持全部范围。它与[点分治方案](solution.zh.md)并列，适合希望减少内存占用的实现。

## 激活一个节点的影响

维护一个激活集合。对每个节点 $u$ ，令 $V_u$ 为其子树内的激活节点数。激活 $y$ 时，只需将根到 $y$ 的整条路径加一。

查询根到 $x$ 的路径和，得到

$$Q(x)=\sum_{u\in A(x)}V_u=\sum_{y\text{ 已激活}}|A(x)\cap A(y)|.$$

这正是已激活节点在 $x$ 的所有祖先子树中的重复计数。按深度处理整组节点：激活本组前求 $L_x$ ，激活整组后求 $U_x$ .设子树大小为 $s_x$ ，总数 $T_x=T_{\operatorname{parent}(x)}+s_x$ 、$T_0=0$ ，输出 $L_x,U_x-L_x,T_x-U_x$ .

## 重链剖分

每个非叶节点选子树最大的儿子为重儿子，其余边为轻边。经过轻边后子树大小至少减半，因此根到任一点只经过 $O(\log n)$ 条重链。

给同一条重链按从上到下的顺序分配连续位置。根路径就能拆成若干位置区间：对当前节点 $x$ ，操作它所在链头到 $x$ 的区间，再跳到链头的父节点，直到根以上。这里仅需链内连续编号，不要求每棵子树在编号中连续。

## 两个树状数组

为了区间加与区间求和，令差分为 $b_i=V_i-V_{i-1}$ .两个树状数组分别保存 $b_i$ 与 $(i-1)b_i$ .前缀和为

$$\sum_{i=1}^rV_i=r\sum_{i=1}^rb_i-\sum_{i=1}^r(i-1)b_i.$$

区间 $[l,r]$ 加一对应 $b_l$ 加一、$b_{r+1}$ 减一，第二数组相应加 $l-1$ 、减 $r$ .两个前缀之差给出区间和。所有数组的加权值和累计值使用 64 位整数。

## 正确性与复杂度

根路径加一恰好增加包含新激活节点的所有子树计数。重链区间不重不漏覆盖根路径，树状数组公式精确实现区间加与区间和。因此查询值就是 $Q(x)$ .再由按深度激活的先后顺序，得到较浅与不更深两类权重和，作差即得到三个答案。

建树、子树大小和重链编号都用显式遍历，支持任意父节点编号及深链。每条路径拆成 $O(\log n)$ 段，每段需要 $O(\log n)$ 的树状数组操作。总时间 $O(n\log^2n)$ ，空间 $O(n)$ .实测最大工作集约 $157.6$ MiB，详见[性能记录](../../../docs/benchmark-R25.json)。GPT-6 应用经典重链剖分与树状数组，提供本题的激活建模、证明、双语说明及实现；这些数据结构本身是通用方法。