题解：P10238 [yLCPC2024] F. PANDORA PARADOXXX

ran_qwq · 2024-03-14 17:01:14 · 题解

删边过程十分地不好搞，考虑先加没被删过的边，再从后往前将删过的边一条一条加回去，在加边的过程中动态维护答案。每次加边合并两棵树 s 和 t。在合并的过程中，树 s 内任意一点 u 和树 t 内任意一点 v 会连通，答案会和 dis(u,v) 取 max。但是，直接暴力更新单次就是 O(n^2) 的，时间复杂度无法承受。

我们容易发现，有很多点对 (u,v) 都不会对答案产生贡献。具体地，设树 s 的一条直径为 x 到 y 的路径，树 t 的一条直径为 p 到 q 的路径，则合并后的树的直径的端点肯定是 x,y,p,q 四点之二。

证明（好像其他题解都没说明白）：

引理：到任意点距离最远的点必是树的一条直径的端点。

证明：

设一棵树根为 r，直径为 x 到 y 的路径，距离 r 最远的一个节点是 z，x 到 y 的 LCA 为 l。不妨设 dis(r,x)\le dis(r,y)。反证法，如果 dis(r,y)<dis(r,z)：

则 dis(l,y)\le dis(r,y)<dis(r,z)，将直径中的 y 换成 z 一定更优，x 到 y 的路径不是直径，矛盾，原命题成立。

• 如果合并后树的直径在树 s 内，则一定是 x 到 y 的路径。
• 如果合并后树的直径在树 t 内，则一定是 p 到 q 的路径。
• 否则直径经过连接树 s 和树 t 的边，由引理，新树直径端点必为 x,y,p,q 四点之二。

综上，证毕。

用并查集合并，求距离可以用 LCA+树上差分。