Difficulty：4.8 / Medium- Tag：LCA，启发式合并，树的直径 显然题目指的就是会连成一个森林。 首先考虑静态树如何查询。 显然，离一个点最远的点是树任意一个直径的两端点。所以找到直径两端点然后 LCA 即可 O(qlog⁡n)O(q\log n)O(qlogn)。 然后考虑讲一个点加入树后，直径有何变化。根据上面的结论，直径要么不变，要么一端变为这个点。 所以我们合并时大小小的树逐个加入到大小大的点即可。 这么做要想让原来的树被合并，新的树得更大才行。所以这样显然最多修改 O(nlog⁡n)O(n\log n)O(nlogn) 个节点（应该吧）。 然后如果你的常数和我一样的话，注意卡常（其实不用卡多少，进行一些简单的优化比如说 vector 换成静态数组即可）。 时间复杂度：O(nlog⁡2n+qlog⁡n)O(n\log^2 n+q\log n)O(nlog2n+qlogn)。