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

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

设深度为 \(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 内，见完整测量。

两种完整范围方案¶

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

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