自动搬运

查看原文

来自洛谷，原作者为

	ran_qwq debug 深入思考 只靠样例与自己！

搬运于2025-08-24 22:56:04，当前版本为作者最后更新于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+树上差分。