题解：Miranda的旅行

题目分析

本题要求在一个动态森林（随着时间逐渐添加边的树）中，多次查询从某个节点出发能到达的最远距离。这实际上是在动态维护树的直径相关信息。

关键观察

1. 树的性质：题目保证任意时刻图都是森林（多棵树），且每棵树都是无环连通图
2. 最远距离：在树中，从任意点 $u$ 出发能到达的最远距离等于 $u$ 到该树直径两端点距离的较大值
3. 动态维护：需要支持动态加边操作和查询操作

解法一：LCT（动态树）【推荐】

思路

使用LCT（Link-Cut Tree） 来维护动态森林，对于每棵树维护：

• 直径的两个端点
• 任意两点间的距离

算法步骤

1. 用LCT维护森林结构，支持link和查询距离
2. 对于每棵树，维护当前直径的端点 $(a,b)$
3. 当连接两棵树时，新直径的端点一定在原来两棵树的直径端点中产生
4. 查询时，计算查询点到当前树直径两端的距离，取最大值

时间复杂度

• 每次操作：$O(\log N)$
• 总复杂度：$O(Q \log N)$

代码框架

struct LCT {
    // LCT标准操作：access, find_root, link, cut, get_distance
};

void solve() {
    LCT lct(n);
    vector<pair<int, int>> diameter(n + 1); // 每棵树的直径端点
    vector<int> belong(n + 1); // 并查集
    
    for (每个操作) {
        if (type == 1) {
            u ^= lastAns, v ^= lastAns;
            // 连接两棵树，合并直径
            merge_diameter(diameter[find(u)], diameter[find(v)], u, v);
            lct.link(u, v);
            union_sets(find(u), find(v));
        } else {
            u ^= lastAns;
            int root = find(u);
            auto [a, b] = diameter[root];
            int dist1 = lct.get_distance(u, a);
            int dist2 = lct.get_distance(u, b);
            lastAns = max(dist1, dist2);
            output(lastAns);
        }
    }
}

解法二：并查集 + 树的直径性质

思路

利用并查集维护连通性，同时维护每棵树的直径信息。

关键性质

当合并两棵树 $T_1$（直径 $a_1-b_1$）和 $T_2$（直径 $a_2-b_2$）时，新直径的端点一定是：

• $a_1, b_1, a_2, b_2$ 中的某两个

实现细节

1. 用并查集维护连通分量
2. 对于每个连通分量，记录直径端点
3. 需要能够快速计算任意两点距离（可用LCA预处理或直接BFS）

时间复杂度

• 每次合并：$O(1)$ 次距离计算
• 距离计算：$O(\log N)$（如果用LCA）
• 总复杂度：$O(Q \log N)$

代码实现要点

1. 数据解密：根据type决定是否对输入进行异或处理
2. 初始状态：开始时所有点都是孤立点，直径就是自身
3. 边界情况：单点树的最远距离为0
4. 距离计算：需要高效计算树上两点距离

总结

本题是经典的动态树直径问题，主要考察：

• 树的直径性质的理解
• 动态数据结构的应用（LCT）
• 对动态森林的维护能力

推荐使用LCT解法，虽然实现复杂但效率高且通用性强。对于竞赛选手，掌握LCT对于解决此类动态树问题非常有帮助。