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

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

激活一个节点的影响¶

维护一个激活集合。对每个节点 \(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，详见性能记录。GPT-6 应用经典重链剖分与树状数组，提供本题的激活建模、证明、双语说明及实现；这些数据结构本身是通用方法。