题解 P1099 【树网的核】

StudyingFather · 2022-02-11 00:24:40 · 题解

在讨论本题的做法前，有必要先分析一下问题的一些特殊性质。

题解区部分题解在性质分析等方面存在一定欠缺，一定程度上可能会影响读者理解做法。

分析

先给出一些记号：

另外，为了方便理解，并使得表意清晰，原题中提到的「树的核」均称为「路径」。

以下引理和定理基于图上所有边权均为正这一前提推出。

引理 1：对于一棵所有边权均为正的树，如果其存在多条直径，则树上必存在一点 p，使得所有直径均经过该点（简单来说，所有直径必交于至少一点）。

证明：用反证法。

如果存在两条直径 D(s,t),D(s^\prime,t^\prime) 不相交，则 \exists a \in D(s,t), b \in D(s^\prime,t^\prime)，且 \forall p \in P(a,b) - \{a, b\}，p \notin D(s, t)，p \notin D(s^\prime, t^\prime)（即，P(a,b) 除了 a,b 两点之外，其他点均不在这两条直径上）。设 d_1 = \max \{P(s,a), P(a,t)\}，d_2 = \max \{P(s^\prime,b), P(b,t^\prime)\}，易知 d_1,d_2 \geq \dfrac{1}{2}D(s, t)，于是 d_1 + d_2 + P(a,b) > D(s,t)，即 d_1,d_2,P(a,b) 这三段拼接成了一条比 D(s,t), D(s^\prime,t^\prime) 这两条直径更长的简单路径，出现了矛盾。\square

（啥，你说可能有三条直径两两相交，但不交于一点的情况？画图后马上就发现有环了。）

定理 1：对于一棵所有边权均为正的树，如果其存在多条直径，则各直径的中点（不一定恰好是某个节点，可能在某条边的内部）是唯一的。

证明：还是用反证法。

设树的两条直径分别为 D(s, t), D(s^\prime,t^\prime)，它们的中点分别为 m, m^\prime，且两个中点不重合。可以推出，m^\prime \in D(s, t)（否则由 引理 1，两直径必定存在一个交点 p。设 d_1 = \max \{P(s,p), P(p,t)\}，d_2 = \max \{P(s^\prime,p), P(p,t^\prime)\}，则 d_1, d_2 > \dfrac{1}{2}D(s, t)，d_1 + d_2 > D(s,t)，与 D(s,t) 是直径矛盾）。

于是实际情况大致如下图所示（略去了树上的其他不必要点，不妨设 m^\prime 位于更靠近 t 的一侧）。

则 P(s,s^\prime) = P(s, m^\prime) + P(m^\prime + s^\prime) > \dfrac{1}{2}D(s, t) + \dfrac{1}{2}D(s^\prime, t^\prime) = D(s,t)，与 D(s,t) 是直径矛盾。\square

引理 2.1：若两条直径有重叠的部分，则于重叠部分同一端点引出的两条直径的非重叠的部分的长度相等。

证明：设两条直径分别为 D(a, c)，D(b, d)，重叠部分为 P(s,t)，如下图所示（P(s,t) 可能是一个点，即 s = t）：

如果 P(a,s) \neq P(b,s)（此时容易得到 P(c,t) \neq P(d,t)），则取 P(a, s) 和 P(b,s) 中较长的一条（长度设为 d_1），P(c, t) 和 P(d,t) 中较长的一条（长度设为 d_2），则由于 d_1 和 d_2 不在同一条直径上（否则推出 D(a,c) > D(b,d)，出现矛盾）则 d_1 + P(s,t) + d_2 > D(a,c)，出现了矛盾。\square

引理 2.2：若路径存在不位于直径上的部分，这条路径对应的偏心距一定不会比全部位于直径上的路径的偏心距的最小值更小。

证明：原命题等价于，对于任意一条不完全位于（或者完全不位于）直径上的路径 F，都存在一条完全位于直径上的路径 F^\prime，使得 \operatorname{ECC}(F) \geq \operatorname{ECC}(F^\prime)。下面是一个构造性的证明。

简单来说，我们采用如下方法构造：对于一条不完全位于（或者完全不位于）直径上的路径 F，找到该路径与直径的一个交点 m（必要时通过延长 F 来找到交点），然后再证明 P(m,m) 这条路径至少不会比 F 更劣。

沿用 引理 2.1 中出现的记号，构建下图（树上的部分节点略去）：

注：

1. 加粗的点一定位于树的某条直径上，未加粗的点一定不位于树的任意一条直径上，即 P(p,v) 这条路径不是树的直径。
2. 其实原图有多少条直径对本引理证明没有影响，图上保留多条直径只是忘记删了。

现在开始讨论。

1. 考虑 P(p,u) 这条路径。距离 P(p,u) 最远的点是哪个点，是 v 吗？因为，P(b,m) + P(m,v) < P(b,m) + P(m,d) = D(b,d)，即 P(m,v) < P(m,d)，因此距离 u 最远的点，是直径的端点，不是 v 这样一个不在直径上的点。
2. 现在考虑 P(u,v) 这条路径。距离 P(u,v) 最远的点是哪个点，是 p 吗？如果 P(p,u) \geq P(a,m)（其余情况同理），则 D(a,c) = P(a,m) + P(m,c) \leq P(p,u) + P(m,c) < P(p,u) + P(u,m) + P(m,c) = P(p,c)，与 D(a,c) 是直径矛盾。因此距离 P(u,v) 最远的点，仍然是直径的端点。
3. 最后考虑 P(m,m) 这条路径。距离 P(m,m) 最远的点是哪个点，是 p 或者 v 吗？注意到 p,v 均不在直径上，于是 P(b,m) + P(m,p) < P(b,m) + P(m,d) = D(b,d)，即 P(m,p) < P(m,d)（这里只举了 p 的情况，v 同理），因此距离 P(m,m) 最远的点，仍然是直径的端点。

（由于直径是树上最长简单路径这一性质，距离上述三条路径最远的点一定不会在从直径上 m 之外的其他点引出的支链上取得，因此这些支链没有画出。）

对于 2 和 3 两种情况，偏心距显然为 \max\{P(a,m), P(m,c)\}，对于 1 这种情况，偏心距为 \max\{P(a,m), P(m,c)\} + P(u,m)。综上，1 和 2 这两种路径完全不位于（或者不完全位于）直径上的方案，不会比 3 这种完全位于直径上的方案更优。\square

因此，虽然原题限制路径只能在直径上取得，但可以忽略这一限制考虑所有满足长度限制的路径，而求得的最小偏心距不变。

定理 2：设在所有满足长度限制的路径中，取得最小偏心距的路径得到的偏心距为 \textrm{minBCC}，则对于任意一条直径，都存在一条长度不超过 s 的路径 F，使得 \operatorname{BCC}(F) = \mathrm{minBCC}。

证明：

沿用 引理 2.1 中出现的记号，构建下图：

注：加粗的点一定位于树的某条直径上，未加粗的点一定不位于树的任意一条直径上，即 P(p,z) 这条路径不是树的直径。

如果我们取 P(c,y) 这条路径，距离该路径最远的点，容易发现不是 p。可能是 z 吗？定理 1 告诉我们，P(t,z) < \dfrac{1}{2}D(a,c)，从而得到 P(x,z) < \dfrac{1}{2}D(a,c)。而 P(a,y) \geq \dfrac{1}{2} D(a,c)，因此排除 z 是最远点的可能性。

（d 是最远点时，P(c,d) 也是树的直径，为了不影响 P(s,t) 是直径重合部分这一前提，这里假定 P(c,d) 不是树的直径。）

综上，这条路径的偏心距 \operatorname{ECC}(P(c,y)) = P(a,y)。简单比较后容易发现，P(t,t) 这条路径偏心距（容易看出是 P(a,t)）一定会更小。

由此得出，当所选路径不包含直径的重合部分时，这条路径一定不是最优路径。

现在考虑所选路径包含直径重合部分的情况。以 P(s,t) 为例，这时候的偏心距 \operatorname{ECC}(P(s,t)) = \max\{P(m,p), P(s,a), P(t,c)\}，如果将 P(s,t) 延伸成 P(s,y) 或者 P(s,q)，偏心距的表达式没有发生变化（仍然存在 P(t,c) 项）。因此，在所选路径包含直径重合部分的时候，直径的选择对答案没有影响。\square

由 定理 2，我们不用在树上的每条直径上都找到取得最小偏心距的路径，只需要在其中一条直径上找即可。

解法

解法一：枚举

先求出树的任意一条直径，然后在直径上枚举路径的端点。

（由 引理 2.2，也可以不用求出树的直径，直接枚举树上的所有路径。）

接下来 DFS 遍历整棵树，按定义求出其他点到路径的距离，从而得到该路径的偏心距。

枚举的时间复杂度 O(n^2)，遍历的时间复杂度为 O(n)，总时间复杂度为 O(n^3)，已经可以通过本题。

解法二：双指针优化枚举

注意到，在固定路径的一端 s 的前提下，随着路径长度的增加，偏心距不会变大。

于是可以考虑枚举路径的一端 s，用双指针的技巧找到距离 s 最远，且不超过路径长度上限的点 t，从而减少候选的最优路径数量。

枚举的过程时间复杂度降到了 O(n)，总时间复杂度为 O(n^2)。

解法三：二分

考虑二分偏心距，将最优化问题变成存在性问题。

定义一端是直径上的点，且只有该点在直径上，其他点都不在直径上的一条链为直径的支链。设 d_i 为从 i 点引出的最长支链的长度。

分析偏心距的可能情况。

以路径 P(2,4) 为例，距离该路径最远的点，可能是 1，5，p。由于 P(1,5) 是直径，q 到 P(2,4) 的距离一定不会比 1 到 P(2,4) 更远，因此在计算偏心距的时候不用考虑 q 点。1,5 是直径的端点，而 p 是路径上的点（除了路径端点）引出的支链的最远点。

归纳一下，设直径上的点分别为 a_1,a_2,\ldots,a_k，取的路径为 P(a_i,a_j)（i \leq j），则所求的偏心距为：\max \{\max_{i < p < j} d_{a_p}, P(a_1,a_i), P(a_j, a_k)\}。

于是我们将偏心距的表达式替换为 \max \{\max_{1 \leq p \leq k} d_{a_p}, P(a_1,a_i), P(a_j, a_k)\}，这一过程中我们加入的项都是不大于 P(a_1,a_i), P(a_j, a_k) 的项，在取 \max 后不会影响结果。