P3629 【巡逻】

Cutest_Junior · 2023-02-20 19:02:08 · 题解

P3629 【巡逻】

题意相当于选两条路径，让它们不相交部分的长度最大。

大多题解的做法都是先选直径、修改权值后再选直径，即默认 其中一条路径就是原树的直径，且大家似乎都没有证明，似乎是唯一意识到这点的@wu3412790 也只给出了另一种做法。这里主要给出证明。

证明

模拟其它题解的做法，设树的一条直径为 AB，选的另一条路径为 CD。若两路径不相交，得到的答案为 d(A,B)+d(C,D)；若两路径相交，如图，

得到的答案为 d(A,C)+d(B,D)（也可能是 d(A,D)+d(B,C)）。

所以可以把题意改为：选两条 没有重复边 的路径，让它们的长度最大。若无特殊说明，之后的叙述都按这个新的题意。

• 引理：如果最优解中的两条路径的其中两个端点分别为 A 和 B，这种做法一定是最优解。
• 证明：若两条路径分别为 AB 和 CD，那显然正确；若两条路径分别为 AC 和 BD，那第二条路径选 CD 也能获得最优解。得证。

那接下来只需要证明：最优解（之一）的两条路径一定有两个端点分别为 A 和 B。

若选的两条路径 C_1D_1 和 C_2D_2 均与 AB 没有重复边，那么把其中任一条改成 AB 一定不会更劣。猜想成立。

若 C_1D_1 与 AB 有重复边而 C_2D_2 没有，把 C_1D_1 改成 AB 也不会更劣，反过来同理。猜想成立。

若两条路径都和 AB 有重复边，如图，

把两条路径分别改为 AD_1 和 BC_2 不会更劣。猜想成立。

综上，若按初始题意，最优解（之一）选择的其中一条路径就是原树的直径。