显然题目的图在任意时刻都是一个森林
当连接两棵树的时候，显然两棵树原来的直径（设为\(l_1,l_2\)）是会被记录在答案中的，假设我们连的点是\(u\)和\(v\)，设\(d_x\)表示\(x\)在其连通块内能走到的最远的距离，那么答案肯定就是要\(max(l_1,l_2,1+d_u+d_v)\)最小
显然\(l_1,l_2\)是固定的，于是我们让\(d_u+d_v\)最小就好了
所以到这里其实已经有一个解法了：对每个并查集维护\(d\)值最小的节点作为树根，更新答案的时候就可以直接更新，而且可以证明，合并之后的集合\(d\)值最小的节点一定是合并之前的两个集合的根节点中的一个，于是我们加边直接加在两个集合的根节点之间就好了
比如，设一个集合的根节点为\(u\)。对于这个集合中一个不是根节点的节点\(x\)考虑，合并之后其的\(d\)值：如果合并后\(x\)的最远路径仍然在原来这个集合中，那么就说明从\(x\)到\(u\)再经过新加的边到另一个集合的最远路径的长度更小，然而从\(x\)到\(u\)再经过新加的边到另一个集合的最远路径的长度显然比从\(u\)经过新加的边到另一个集合的最远路径的长度长，于是合并后\(x\)的最远路径比从\(u\)经过新加的边到另一个集合的最远路径的长度长，根据合并之前根节点的性质，合并后\(x\)的最远路径仍然比合并前\(u\)的最远路径长，于是合并后\(d_x\)一定大于\(d_u\)；对于合并后\(x\)的最远路径经过新加的边仍然可以这么讨论。证毕
但是，根据BFS求树的直径的第一步操作，我们可以知道对任意节点的\(d\)所代表的路径的终点一定是一条直径的一端，于是我们画出直径，就不难得出题解的贪心结论了
所以以后在遇到“一个点在这棵树所能走的最远的距离”一定要联想到树的直径的一个端点，说不定就能简化问题
标签：路径,公园,合并,新加,集合,HXY,节点,最远 From： https://www.cnblogs.com/dingxingdi/p/18214379