HXY 造公园 题解

思路

初始图是森林，而每次有效操作 2 只连接两个不同的连通分量，所以每个连通区域始终是一棵树。查询的答案就是树的直径。

对于直径为 $d$ 的树，任意点到树中其他点的最大距离称为该点的离心率。树的最小离心率，即半径，为

$$\left\lceil\frac d2\right\rceil.$$

树的中心恰好达到这个半径。

设要合并的两棵树直径分别为 $d_1,d_2$，选择端点 $u,v$ 连接。合并后的最长路径可能完全位于原树中，也可能经过新边。经过新边的最长路径长度为

$$\operatorname{ecc}_1(u)+1+\operatorname{ecc}_2(v).$$

选择两棵树各自的中心可以使这一项最小。因此最优合并后的直径为

$$\max\left( d_1,\ d_2,\ \left\lceil\frac{d_1}{2}\right\rceil+ \left\lceil\frac{d_2}{2}\right\rceil+1 \right).$$

子任务 1 没有合并操作。对每棵初始树进行两次遍历求直径，即可回答所有查询。

子任务 2 可以枚举两棵树之间的全部端点对，实际加入使新直径最小的边，再用广度优先搜索枚举点对距离。

子任务 3 可以用两次广度优先搜索找到每棵树的直径路径及中心，显式连接两个中心，然后重新遍历合并后的树求直径，复杂度为 $O(qn)$。

满分做法只维护每个连通分量的直径，不需要保存后来选择的具体边。

做法

先用并查集建立初始连通分量。对每棵初始树任选一点开始遍历，找到最远点 $a$；再从 $a$ 遍历一次，得到的最大距离就是该树直径。把直径记录在并查集根上。

处理操作：

• 操作 1：找到 $x$ 的并查集根，输出该根记录的直径。
• 操作 2：找到 $x,y$ 的根。若相同则忽略；否则用上式计算新直径，合并两个并查集，并把新直径记录到新根。

整数表达式 $(d+1)/2$ 恰好等于 $\lceil d/2\rceil$。

正确性证明

首先证明合并公式的下界。无论如何选择新边端点，合并后的树仍包含两棵原树，所以新直径至少为 $d_1$ 和 $d_2$。此外，第一棵树任意连接点的离心率至少是其半径 $\lceil d_1/2\rceil$，第二棵树同理。因此经过新边的某条路径长度至少为

$$\left\lceil\frac{d_1}{2}\right\rceil+ \left\lceil\frac{d_2}{2}\right\rceil+1.$$

再证明该下界可以达到。分别选择两棵树的中心连接。此时任意经过新边的路径长度不超过两棵树半径之和再加 $1$；不经过新边的路径分别不超过 $d_1,d_2$。所以合并后直径不超过公式右侧。结合下界，公式成立。

初始阶段的两次树遍历正确求出每个初始连通分量的直径。之后归纳考虑每次操作：查询直接读取所在分量的已知直径，答案正确；无效合并不改变图；有效合并按已证公式计算唯一需要维护的新直径，并查集合并后仍把它关联到整个新分量。因此所有操作后的直径记录始终正确。

复杂度分析

初始求直径总计遍历每个点和每条边常数次，复杂度为 $O(n+m)$。每次操作只做常数次并查集操作，均摊复杂度为 $O(\alpha(n))$。

总时间复杂度为 $O(n+m+q\alpha(n))$，空间复杂度为 $O(n+m)$。