[POI 2014] HOT-Hotels 加强版 题解

思路

树上任意三个点都有唯一的中位点，也就是三条两两路径的公共交点。三个点两两距离相等，当且仅当它们到这个中位点的距离相同，并且分别位于中位点的三个不同邻接分支中。因此可以按中位点和距离统计答案。

当 $n$ 较小时，可以枚举中位点。依次处理它的各个邻接分支，统计该分支中每个距离上的点数。对固定距离维护此前分支的点数和两分支点对数；加入新分支时，已有点对数乘以新分支点数就是新增三元组数。每个中位点遍历整棵树一次，总复杂度为 $O(n^2)$。

满分做法把树根定为 $1$。令 $f_{u,d}$ 表示 $u$ 的子树中距 $u$ 为 $d$ 的点数。再维护辅助量 $g_{u,d}$，它表示已经处理的分支中，能够在以后与距当前结点相应距离的第三个点组成合法三元组的点对数。合并儿子 $v$ 时，$v$ 中深度为 $d$ 的点在 $u$ 看来深度为 $d+1$。

在把一个轻儿子合并进当前结点前，有两类跨分支贡献：当前已处理分支中的点对与轻儿子中的单点配对，以及当前已处理分支中的单点与轻儿子内部已经形成的点对配对。随后再更新跨分支点对数、继承轻儿子内部点对，并累加深度计数。所有下标移动都只来自深度增加一这一事实。

若直接复制每个结点的数组，链上会退化为平方复杂度。选择最高的儿子作为长儿子，让它的数组与父亲共享连续存储，只移动首指针；其余轻儿子的数组各自开辟空间并逐项合并。每条重链只分配一次空间，而每个轻子树的数组只在对应轻边处扫描一次，所有扫描长度之和为线性，因此可以在线性时间内完成上述转移。

答案最大不超过 $\binom{n}{3}$，需要使用 64 位整数。

做法

1. 从点 $1$ 出发建立父子关系，按逆序求出每个结点的最大子树深度，并选出最高的儿子作为长儿子。
2. 为每条重链分配连续的深度计数数组和点对数组；长儿子直接复用父亲数组的偏移位置，轻儿子使用独立区间。
3. 按后序处理结点。先继承长儿子的状态，加入结点自身，再逐个合并轻儿子。
4. 每次合并先统计两类新三元组，再更新点对数组与点数数组，避免同一分支被重复选取。
5. 所有结点处理完后输出累计答案。

复杂度

小规模做法的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

满分做法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。