# 祖先子树的分层统计：距离和与点分治

## 把重复计数化为两点权重

设深度为 $d_x$ ，子树大小为 $s_x$ .节点 $y$ 同时属于多少个 $x$ 的祖先子树？这些子树的根恰是 $x,y$ 的公共祖先，也就是最近公共祖先 $\operatorname{lca}(x,y)$ 及其全部祖先。因此 $y$ 的权重为

$$w(x,y)=d_{\operatorname{lca}(x,y)}+1.$$

三项答案之和可以直接算：令 $T_0=0$ ，则 $T_x=T_{\operatorname{parent}(x)}+s_x$ .接下来只需分别计算深度严格小于与不大于 $d_x$ 的节点的权重和。

## 用距离表达权重和

对一个已激活的节点集合 $B$ ，维护节点数 $C$ 、深度和 $H$ ，以及从查询点 $x$ 到它们的树上距离和 $D(x)$ .由

$$\operatorname{dist}(x,y)=d_x+d_y-2d_{\operatorname{lca}(x,y)}$$

得到

$$\sum_{y\in B}w(x,y)=\frac{(d_x+2)C+H-D(x)}2.$$

分子一定是偶数，这里进行普通整数除法，不涉及模运算。

按原树深度从小到大处理，每次处理完整的一层。激活本层前查询得到 $L_x$ ；激活本层全部节点后，再查询得到 $U_x$ .答案依次为 $L_x,U_x-L_x,T_x-U_x$ .必须先完成整层的第一次查询，再整体激活，避免同深节点被错误计入较浅部分。

## 点分治维护动态距离和

每个连通块选一个重心：删除它后，每个子块至多为原块一半。递归处理子块，得到深度 $O(\log n)$ 的点分树。对每个节点记录它到各点分祖先的原树距离。

在点分中心 $c$ 维护：

- $A_c$ ：属于其点分子树的激活节点数。
- $B_c$ ：这些节点到 $c$ 的距离和。
- 对点分子节点 $b$ ，另存 $A'_b,B'_b$ ，统计位于该子块的激活节点；$B'_b$ 的距离以其**父中心**为起点。

插入 $y$ 时沿点分祖先链更新 $A_c,B_c$ ，并更新对应的下一子块统计。查询 $x$ 时沿同一链，对每个中心加入 $B_c+A_c\operatorname{dist}(x,c)$ ；若 $x$ 位于其子块 $b$ 内，再减去 $B'_b+A'_b\operatorname{dist}(x,c)$ .

为什么正确？对任意激活点 $y$ ，它与 $x$ 首次处于同一中心的不同子块，或其中一点就是该中心时，原树路径经过这个中心。这一层的相加项给出真实距离。更高层中二者属于同一子块，相加后会被减去；更低层不同时包含二者。因此每个 $y$ 的距离恰好贡献一次。

## 正确性与实现

点分治正确维护 $D(x)$ ，距离恒等式给出任意激活集合的权重和。按深度分组使两次查询分别覆盖严格较浅与不更深的节点；再用总数作差，就得到题面要求的三项重复计数。

程序用广度遍历得到深度顺序，用逆序累计子树大小。输入父节点编号可能较大，不能按编号递推。各连通块的遍历使用显式数组，只有点分治本身递归，深度为 $O(\log n)$ ，所以原树为长链时也不会形成线性递归栈。

每个点到每层点分中心的距离保存为 32 位整数；统计和答案使用 64 位整数，单个答案至多 $n^2$ .建点分树、所有插入和两次查询合计 $O(n\log n)$ 时间、$O(n\log n)$ 空间。最大数据实测峰值约 $350.4$ MiB，在给定 $512$ MB 内，见[完整测量](../../../docs/benchmark-R25.json)。

## 两种完整范围方案

首选 [std.cpp](std.cpp) 使用点分治，给出 $O(n\log n)$ 时间界。[重链剖分方案](solution-alternative.zh.md)与 [alternative.cpp](alternative.cpp) 用 $O(n)$ 空间、$O(n\log^2n)$ 时间，作为有明确空间优势的并列方案。参考环境中，最慢中位数分别约 $6.83$ 秒和 $5.51$ 秒；重链方案在这些数据上的实际时间也较短，不能仅凭渐进式判断常数。两者均通过完整数据与统一时限，其他平台需重新测量。

材料没有给出可用解法或求解程序。GPT-6 用经典 LCA 距离恒等式、点分治及重链剖分组织这两套算法，补齐证明和 C++17 实现。小树用祖先集合交集逐对核对；正式数据双程序逐项对拍，链与星形用闭式核对全部输出，其余大树另以直接遍历核对选定节点，并检查全部节点的三项总数。