关于本题题解的补充证明

· · 题解

补充证明

题解区有一些题解用到了这样一个结论：

对于树 \Gamma = (V, E)，u, v, w \in V 使得 \mathrm d(u, v) = \mathrm d(v, w) = \mathrm d(u, w)，则存在 c 使得 \mathrm d(c, u) = \mathrm d(c, v) = \mathrm d(c, w)。

但是均没有给出证明。下面是一个证明：

设点 x 使得 \mathrm d(u, x) + \mathrm d(v, x) + \mathrm d(w, x)（记为 A(x)）最小。将 \Gamma 按照 x 为根变为一棵有根树，则我们有 \mathrm{lca}(u, v) = \mathrm{lca}(v, w) = \mathrm{lca}(u, w) = x（否则若其中一个不为 x，记为 y，则将 x 改为 y 会将 A(x) 的两项减少 1，一项增加 1，与 x 使得 A(x) 最小矛盾），这样根据 \mathrm{d}(u, v) = \mathrm{dep}(u) + \mathrm{dep}(v) - 2 \mathrm{dep}(\mathrm{lca}(u, v))，可知 \mathrm{dep}(u) + \mathrm{dep}(v) = \mathrm{dep}(u) + \mathrm{dep}(w) = \mathrm{dep}(v) + \mathrm{dep}(w)，适当变形可知 \mathrm{dep}(u) = \mathrm{dep}(v) = \mathrm{dep}(w)，即 \mathrm d(x, u) = \mathrm d(x, v) = \mathrm d(x, w)

本题解法

对于一个 \mathrm d(u, v) = \mathrm d(v, w) = \mathrm d(u, w) 的三元组 (u, v, w)，考虑上述证明构造的 A 函数，则 A(x) 最小的 x 唯一。（证明：考虑到使得 A(x) 最小的 x，必然是 u \to v 唯一路径的中点。）

因此考虑枚举这个 x 作为根，因此我们只需要考虑三元组 (u, v, w)，使得：

对于枚举的特定深度 \delta，考虑 E_y~(y \in \mathrm{child}(x)) 为 y 的子树内深度为 \delta 的点的个数，因此我们需要计算

\sum_{\{a, b, c\} \subseteq \mathrm{child}(x), |\{a, b, c\}| = 3} E_a E_b E_c.

首先尝试将 3 换成 2，不难发现答案为

\sum_{i} A_i \left(\sum_{j < i} A_j\right),

动态维护 \sum\limits_{j<i}A_j 即可。这启发我们如果考虑

\Sigma_0(i) = 1,\Sigma_1(i) = \sum\limits_{j < i}A_j \Sigma_0(j), \Sigma_2(i) = \sum_{j < i} A_j \Sigma_1(j),\Sigma_3(i) = \sum_{j < i} A_j \Sigma_2(j),

则 \Sigma_3 就是答案。而动态地维护各个 \Sigma_k(i) 即可。

注意到对于每个根 x，每个点只会被统计一次，所以时间复杂度是 \Theta(n^2) 的，可以通过。