B

M市一共有$n$个林场，从$1$到$n$编号。由于M市特殊的道路规划，这$n$个林场通过$n-1$条双向道路连接。任意两个林场都可以互相到达，也就是说，这$n$个林场形成了一棵树。

然而，最近的大火蔓延了这$n$个林场。你是森林的管理员，想尽快扑灭这场森林大火。但是，你人手有限，只有一个消防队，所以你非常着急。在这种情况下，你拿出了保留多年的魔法：

首先，你会选择一个初始林场，将唯一的消防队派往这个初始林场。该消防队到达初始林场所需要的时间是1小时。

然后，在过后的每一小时，这个消防队会克隆出一个完全一样的消防队，新克隆出的消防队会沿着道路前往相邻的林场。这个消防队在到达相邻的林场后，同样会在之后的每个小时都克隆出新的消防队，新的消防队会前往相邻的林场。克隆过程会一直继续，直到所有林场都至少有一支消防队。也就是说，只要存在林场没有消防队，已有的消防队都会进行克隆。

作为森林管理员，尽管你已经有了魔法，但是你还是非常着急，想知道：要想让所有林场都至少有一支消防队，你最少需要多少个小时。此外，你还需要输出，你选择的初始林场的编号。可能不止一个林场可以当作初始林场，如果这样，请输出所有可以当作初始林场的林场。

输入格式:

输出格式:

样例:

样例1.

样例2.

提示:

输入格式:

输出格式:

样例:

样例1.

提示:

输入格式:

第一行三个整数$n,m$表示树的大小，事件数量（$n,m \le 2 \times 10^5$）

接下来$n-1$行每行两个整数表示一条树边

接下来$m$行，每行表示一个操作：

• $1$ $u$ $v$表示添加一条路径$u-v$
• $2$ $id$表示删除加入的第$id$条路径，保证这条路径存在并且没有被删除

输出格式:

输出$m$行，每行一个整数表示每个操作之后的答案最远距离最小是多少。

样例:

样例1.

2

三题 Editorial

以下推导仅使用所提供的题面和样例。每题给出思路、正确性证明、复杂度和完整 C++23 实现。

第一题：森林消防队

题意中的歧义

本题按已经确认的、与样例一致的模型处理：每个已经有消防队的林场，每小时最多向一个尚未覆盖的相邻林场派出新队伍；新到达的队伍从下一小时开始扩展。

原题“已有的消防队都会进行克隆”若允许反复向已经覆盖的林场增援，就会出现另一种模型。以样例 2 为例，从点 $1$ 出发：第 2 小时到达 $3$；第 3 小时，点 $1$ 再向 $3$ 派队，点 $3$ 向 $4$ 派队；第 4 小时，点 $1$ 覆盖 $2$，点 $3$ 的两队分别向 $4,8$ 派队，点 $4$ 向 $5$ 派队；第 5 小时，点 $4$ 的两队分别覆盖 $6,7$。这样点 $1$ 也能在 5 小时内完成，与样例输出的起点集合不符。下文不采用这个允许增援的模型。

1. 固定起点后，问题变成子树之间的调度

先把初始林场作为根。一个非根节点只能先由父亲覆盖，然后才能覆盖自己的子树。

假设点 $u$ 已经有了队伍，它有三个儿子。三个儿子在各自第一次收到队伍后，还分别需要 $4,1,3$ 小时才能覆盖自己的子树。

如果依次启动耗时为 $4,3,1$ 的三个儿子，完成时刻分别是 $1+4,2+3,3+1$，所以 $u$ 的整棵子树再过 $5$ 小时就全部完成。

每个儿子一旦启动，就独立扩展。点 $u$ 只负责决定启动顺序。

2. 耗时长的儿子应当先启动

设相邻两个启动位置为 $t,t+1$，两个子树的剩余耗时分别为 $a,b$，其中 $a\ge b$。

先启动 $b$ 时，这两个子树的最晚完成时刻为 $t+1+a$。交换成先启动 $a$ 后，最晚完成时刻为 $\max(t+a,t+1+b)$，不会更大。

不断交换这样的相邻逆序对，就得到按剩余耗时从大到小的最优顺序。

设排好序的儿子耗时为 $x_1\ge x_2\ge\cdots\ge x_k$，则

$$ f(u)=\max_{1\le i\le k}(x_i+i). $$

没有儿子时，$f(u)=0$。这里不计点 $u$ 自己第一次到达所需的时间。

因此，如果只问一个固定起点，可以自底向上计算这棵有根树。

3. 为每条边计算两个方向的答案

定义 $F(u\mid p)$：删去边 $u-p$ 后，假设点 $u$ 已经有队伍，覆盖 $u$ 所在连通块还需要的最少时间。

点 $u$ 的每个邻居 $v\ne p$，都对应一个待启动分支，其耗时为 $F(v\mid u)$。把这些值降序排列后，仍然使用刚才的转移式。

如果知道 $u$ 所有邻居传来的值，就能计算：

• 以 $u$ 为起点的总时间；
• $u$ 向每个邻居传出的值 $F(u\mid v)$。

任选点 $1$ 为根，分两遍处理：第一遍自底向上求出儿子传给父亲的值；第二遍自顶向下补出父亲传给儿子的值。

4. 删去一个分支，用前后缀最大值计算

设点 $u$ 的全部邻居传来的值已经排成 $x_1\ge\cdots\ge x_d$。

定义

$$ P_i=\max_{1\le j\le i}(x_j+j),\qquad S_i=\max_{i\le j\le d}(x_j+j). $$

约定 $P_0=S_{d+1}=0$。

如果删去排在第 $i$ 位的分支，它前面的分支启动时刻不变，后面的分支都提前一小时。因此

$$ F(u\mid v_i)=\max(P_{i-1},S_{i+1}-1). $$

每个方向的转移都只需要 $O(1)$。实现时只保存后缀数组，前缀最大值边扫描边维护即可。以 $u$ 为起点的总时间为 $1+P_d$，其中的 $1$ 是最初到达林场 $u$ 的时间。

正确性证明

对于任意固定父边，覆盖点 $u$ 后，不同分支之间相互独立。每个分支的第一次启动必须占用点 $u$ 的一个小时，且没有必要空等。交换论证说明，按照分支剩余耗时降序启动能够达到最短完成时间，所以递推式精确计算了 $F(u\mid p)$。

第一遍遍历按从叶到根的顺序应用这个递推，正确得到所有儿子到父亲的值。第二遍遍历处理点 $u$ 时，父亲方向的值已经得到，儿子方向的值也已在第一遍得到。前后缀公式恰好计算删去任意一个邻居后的最优值，因此第二遍又能正确算出每条父亲到儿子的值。

于是每个起点的最短总时间都被精确计算。取其中最小值，并按编号扫描输出所有达到最小值的点，即为所求。

复杂度与实现要点

点 $u$ 的排序代价为 $O(\deg(u)\log\deg(u))$，由 $\sum_u\deg(u)=2n-2$，总时间为 $O(n\log n)$，空间为 $O(n)$。

使用显式遍历序列，避免长度为 $2\times10^5$ 的链导致递归栈溢出。$n=1$ 时答案为 1，唯一可选起点为 1。

C++23 实现

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<int>> graph(n + 1);
    for (int i = 2, a; i <= n; ++i) {
        cin >> a;
        graph[i].push_back(a);
        graph[a].push_back(i);
    }
    vector<int> parent(n + 1), order{1}, down(n + 1), up(n + 1);
    for (int k = 0; k < n; ++k) {
        int u = order[k];
        for (int v : graph[u]) if (v != parent[u]) {
            parent[v] = u;
            order.push_back(v);
        }
    }
    for (int k = n - 1; k >= 0; --k) {
        int u = order[k];
        vector<int> values;
        for (int v : graph[u]) if (v != parent[u]) values.push_back(down[v]);
        sort(values.rbegin(), values.rend());
        for (int i = 0; i < (int)values.size(); ++i) {
            down[u] = max(down[u], values[i] + i + 1);
        }
    }
    vector<int> answer(n + 1);
    for (int u : order) {
        vector<pair<int, int>> values;
        for (int v : graph[u]) {
            values.emplace_back(v == parent[u] ? up[u] : down[v], v);
        }
        sort(values.rbegin(), values.rend());
        int d = (int)values.size();
        vector<int> suffix(d + 2);
        for (int i = d; i >= 1; --i) {
            suffix[i] = max(suffix[i + 1], values[i - 1].first + i);
        }
        answer[u] = suffix[1] + 1;
        int prefix = 0;
        for (int i = 1; i <= d; ++i) {
            int v = values[i - 1].second;
            if (v != parent[u]) up[v] = max(prefix, suffix[i + 1] - 1);
            prefix = max(prefix, values[i - 1].first + i);
        }
    }
    int best = *min_element(answer.begin() + 1, answer.end());
    cout << best << '\n';
    bool first = true;
    for (int u = 1; u <= n; ++u) if (answer[u] == best) {
        if (!first) cout << ' ';
        cout << u;
        first = false;
    }
    cout << '\n';
}

第二题：C — 相邻循环交换

1. 先固定每个字符的身份

允许的交换为 $\texttt{AB}\to\texttt{BA}$、$\texttt{BC}\to\texttt{CB}$、$\texttt{CA}\to\texttt{AC}$。

把字符看成有独立编号的物品。同一对物品一旦交换，其顺序就变成不允许交换的方向，所以同一对物品最多交换一次；其他交换也不会改变这一对物品的相对顺序。

因此，操作次数就是最终发生交换的字符对数量，过程一定有限。

为了统一表示，记循环次序为 $\texttt{A}\to\texttt{B}\to\texttt{C}\to\texttt{A}$。对字符 $X$，记它的后继为 $\operatorname{next}(X)$，前驱为 $\operatorname{prev}(X)$。

2. 中间存在第三种字符的字符对，永远不能交换

考虑初始顺序为 $X\cdots Y$、且 $XY$ 允许交换的两个字符。设第三种字符为 $Z$。

如果两者之间有一个 $Z$，初始顺序就是 $X\cdots Z\cdots Y$。其中 $XZ$ 和 $ZY$ 都不允许交换，所以这两个相对顺序永远保持，$X,Y$ 就无法相遇。

反过来，如果两者之间只有 $X,Y$，仅在这段二字符子串内执行交换，就能够让这对 $X,Y$ 交换。

因此，把满足以下条件的字符对称为“潜在交换对”：左边是 $X$，右边是 $\operatorname{next}(X)$，并且两者之间没有第三种字符。

所有实际操作都对应潜在交换对，但这些交换对不一定能同时实现。例如 $\texttt{ABC}$ 中，$\texttt{AB}$ 和 $\texttt{BC}$ 都是潜在交换对，最多却只能选一对。

3. 每个字符只能向一个方向移动

一个字符 $X$ 向左移动时，交换的是左边的 $\operatorname{prev}(X)$；向右移动时，交换的是右边的 $\operatorname{next}(X)$。

如果同一个字符两种移动都发生，就存在初始顺序为 $\operatorname{prev}(X),X,\operatorname{next}(X)$ 的三个物品，并要求两端最终都越过中间的 $X$。但这三个物品的两端相对顺序不能交换，这两个要求互相矛盾。

所以，可以为每个字符选择一个方向 $L$ 或 $R$。某个潜在交换对只有在左端选 $R$、右端选 $L$ 时才可能实现。

暂时只最大化满足方向要求的潜在交换对数量，得到原问题的一个上界；后面会证明这个上界能够达到。

4. 相同的连续字符可以统一选择方向

将字符串压缩为 $k$ 个字符段，第 $i$ 段的字符为 $c_i$，长度为 $w_i$。

同一段中的所有字符拥有完全相同的段外潜在交换对象，而段内没有交换。固定其他字符的方向后，这一段每个字符选 $L$ 或 $R$ 的贡献完全相同。所以总可以把整段统一改成贡献更大的方向，且不会让上界下降。

逐段调整后，就得到一个“每段统一选择方向”的最优上界方案。

只有同时具有左右交换机会的段需要决策，称为“可选段”。其左侧相邻段必须是 $\operatorname{prev}(c_i)$，右侧相邻段必须是 $\operatorname{next}(c_i)$，直接看左右邻段就能判断。其余段选择唯一有贡献的方向即可。

5. 一遍扫描，直接计算最大收益

只需要记住最近的一个可选段：若两个可选段之间存在潜在交换对，中间只能出现这两种字符；内部段的两侧邻段字符相同，不可能也是可选段。因此，能发生相互作用的可选段在可选段序列中必然相邻。

用 $0,1,2$ 表示 $\texttt{A},\texttt{B},\texttt{C}$，下标对 3 取模。扫描字符段，维护：

• $dp_L,dp_R$：最近可选段分别选 $L,R$ 时，已经扫描到的字符对产生的最大收益。
• $\mathrm{fixed}[c]$：尚未被第三种字符阻断的、非可选段中的字符 $c$ 数量。
• $\mathrm{optional}[c]$：最近可选段尚未被阻断的字符数量，只有至多一个位置非零。

处理当前字符为 $c$、长度为 $w$ 的段，其潜在交换左端字符为 $c+2$。令

$$ g=w\cdot\mathrm{fixed}[c+2],\qquad h=w\cdot\mathrm{optional}[c+2]. $$

$g$ 来自方向固定的左端；$h$ 只有最近可选段选 $R$ 时才能取得。

如果当前段不是可选段，只要有左侧交换机会，其方向就必然为 $L$，于是

$$ dp_L\mathrel{+}=g,\qquad dp_R\mathrel{+}=g+h. $$

再将 $w$ 加入 $\mathrm{fixed}[c]$。即使这一段只能向左移动，加入也无妨：它没有合法的未来右侧交换对象，对应计数会在被使用前清零。

如果当前段是新的可选段，则将 DP 状态改为记录它的方向：

$$ \begin{aligned} ndp_L&=\max(dp_L,dp_R+h)+g,\\ ndp_R&=\max(dp_L,dp_R). \end{aligned} $$

选 $L$ 时可以取得左侧收益；选 $R$ 时，其收益要等未来右端出现才统计。然后清空旧的 $\mathrm{optional}$，设置 $\mathrm{optional}[c]=w$。旧可选段无法再与之后的新段形成潜在交换对，否则这两段之间就不可能夹着当前可选段。

无论属于哪一类，最后都清零 $\mathrm{fixed}[c+1]$ 和 $\mathrm{optional}[c+1]$：当前字符 $c$ 是交换类型 $(c+1)\to(c+2)$ 的第三种字符，会阻断之前累计的左端。

初始两个 DP 都为 0，最终答案为 $\max(dp_L,dp_R)$。每个字符对只在扫描到右端时统计一次。

例如 $\texttt{ABCCA}$ 的可选段为 $\texttt{B}$ 和 $\texttt{CC}$。扫到它们后，$(dp_L,dp_R)$ 依次为 $(1,0)$、$(2,1)$；扫到最后的 $\texttt{A}$ 时，只有第二种状态能再取得 $2$ 次交换，最终答案为 $3$。

6. 为什么这个上界一定能够达到

还需要证明，不能只凭“方向相容”就直接把所有交换机会相加。

固定上述逐段选择的方向。对每个潜在交换对，当且仅当左端选 $R$、右端选 $L$ 时，规定最终反转这一对的顺序；其他字符对保持原顺序。

我们证明这些规定能够形成一个合法的最终排列。考虑初始位置满足 $i

第一，不可能同时要求反转 $(i,j)$ 和 $(j,t)$，因为这会要求物品 $j$ 同时选 $L,R$。

第二，如果要求反转 $(i,t)$，设其字符为允许交换的 $X,Y$。中间不可能有第三种字符，所以位置 $j$ 的字符只能是 $X$ 或 $Y$。

• 如果是 $X$，它与左端同段时也选 $R$；不同段时，其左侧相邻段为 $Y$，使它没有向左交换的机会，因此也选 $R$。于是 $(j,t)$ 同样要求反转。
• 如果是 $Y$，它与右端同段时也选 $L$；不同段时，其右侧相邻段为 $X$，使它没有向右交换的机会，因此也选 $L$。于是 $(i,j)$ 同样要求反转。

这两点排除了三个物品的顺序要求形成环的全部可能。因此，这些两两顺序构成一个合法排列。

从初始串出发，按这个目标排列进行相邻交换排序。每次只交换与目标顺序相反的相邻物品；这些物品恰好是规定要反转的潜在交换对，其当前顺序仍然是允许的 $XY$，所以每一步都合法。每个规定反转的字符对恰好交换一次。

因此，方向方案计算出的交换对数量全部能够实现。结合前面的上界和最优 DP，算法得到的就是最大操作次数。

复杂度与实现要点

字符段压缩后，一遍扫描完成计数和 DP，总时间为 $O(n)$。压缩数组占 $O(n)$ 空间，DP 和计数器只占 $O(1)$ 额外空间。多组数据的总时间为 $O(\sum n)$。

操作次数可能达到平方级，例如 $\texttt{A}^{n/2}\texttt{B}^{n/2}$，所有计数乘积和 DP 均使用 64 位整数。

C++23 实现

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        string s;
        cin >> n >> s;
        vector<int> color, count;
        for (char ch : s) {
            int c = ch - 'A';
            if (!color.empty() && color.back() == c) ++count.back();
            else {
                color.push_back(c);
                count.push_back(1);
            }
        }
        int k = (int)color.size();
        array<i64, 3> fixed{}, optional{};
        i64 left = 0, right = 0;
        for (int i = 0; i < k; ++i) {
            int c = color[i];
            i64 gain = count[i] * fixed[(c + 2) % 3];
            i64 join = count[i] * optional[(c + 2) % 3];
            bool choice = i > 0 && i + 1 < k
                && color[i - 1] == (c + 2) % 3 && color[i + 1] == (c + 1) % 3;
            if (choice) {
                // New optional run: left gains incoming pairs; right gains none yet.
                i64 next_left = max(left, right + join) + gain;
                i64 next_right = max(left, right);
                left = next_left;
                right = next_right;
                optional.fill(0);
                optional[c] = count[i];
            } else {
                left += gain;
                right += gain + join;
                fixed[c] += count[i];
            }
            // c blocks previous occurrences of c+1 from meeting a future c+2.
            fixed[(c + 1) % 3] = optional[(c + 1) % 3] = 0;
        }
        cout << max(left, right) << '\n';
    }
}

第三题：D — 动态路径中心

1. 维护整组路径的距离函数

设当前路径集合为 $\mathcal S$，定义

$$ f_{\mathcal S}(x)=\max_{P\in\mathcal S}\operatorname{dist}(x,P). $$

题目要求每次增删之后求 $\min_x f_{\mathcal S}(x)$。

两组路径合并时，距离函数逐点取最大值。下面证明，这个函数始终可以用“一条路径”或“两个点”表示，从而直接放在线段树上维护。

题面未明确路径集合为空时的输出。实现约定此时答案为 0；如果原题保证集合非空，则不会用到这个分支。

2. 两条相交路径：压缩为它们的交集

如果路径 $P,Q$ 相交，交集 $I=P\cap Q$ 仍然是一条路径，允许只有一个点，并且对任意点 $x$，有

$$ \max(\operatorname{dist}(x,P),\operatorname{dist}(x,Q)) =\operatorname{dist}(x,I). $$

设 $t$ 是交集上离 $x$ 最近的点。从 $x$ 走向 $t$，至少要到 $t$ 才进入其中一条路径，否则两条路径在 $t$ 之前就已有交集。故左边正好等于 $\operatorname{dist}(x,t)$。

3. 两条不相交路径：压缩为最近的一对点

如果 $P,Q$ 不相交，设连接它们的最短路径两端为 $p\in P,q\in Q$，距离为 $D$。那么对任意点 $x$，有

$$ \max(\operatorname{dist}(x,P),\operatorname{dist}(x,Q)) =\max(\operatorname{dist}(x,p),\operatorname{dist}(x,q)). $$

令 $c$ 是 $p-q$ 的中点，证明时允许边内点。删去 $c$ 后，$P,Q$ 位于不同方向；至少有一个方向与 $x$ 不同，到那条路径的距离为 $\operatorname{dist}(x,c)+D/2$，另一条路径的距离不超过此值。上式两边都等于

$$ \operatorname{dist}(x,c)+\frac D2. $$

所以两条不相交路径可以替换成两个单点路径 $p,q$。实现只保存原树上的这两个点，不需要真的建立边中点。

4. 最远的一对路径足以支配其余路径

设一组路径的最大两两距离为 $D>0$，由 $P,Q$ 取得，最短连接路径中点为 $c$。对任意其他路径 $R$，有

$$ \operatorname{dist}(c,R)\le\frac D2. $$

否则，$R$ 不经过 $c$，至少与 $P,Q$ 中的一条分居 $c$ 两侧，它们的距离大于 $D$，矛盾。

于是对任意 $x$，根据三角不等式，

$$ \operatorname{dist}(x,R) \le\operatorname{dist}(x,c)+\operatorname{dist}(c,R) \le\operatorname{dist}(x,c)+\frac D2. $$

右边正是 $P,Q$ 产生的函数，故这对最远路径已经支配整组路径。

注意这里要求 $D>0$。所有路径相交时应当维护交集，不能随便挑两条路径代替整组路径。例如三叉树上连接两两叶子的三条路径，任意两条的交集可能是一条边，三条的公共交集却只有中心。

5. 每个线段树节点只需要两种非空状态

例如在链 $1-2-3-4$ 上，路径 $[1,2]$ 与单点路径 $[4,4]$ 可以替换为两个点 $2,4$；最佳选点是 $3$，答案为 $1$。一般地维护：

• 路径状态 $\operatorname{Path}(a,b)$：表示函数 $\operatorname{dist}(x,[a,b])$。
• 双点状态 $\operatorname{Pair}(a,b)$：表示函数 $\max(\operatorname{dist}(x,a),\operatorname{dist}(x,b))$，其中 $a\ne b$。

另有空状态，合并时直接返回另一边。

下面分别处理三种合并。

路径 + 路径

两条路径相交时返回交集路径；不相交时，返回最短连接路径的两个端点。

双点 + 路径

合并 $\operatorname{Pair}(a,b)$ 和路径 $P$，等价于合并三条路径 $\{a\},\{b\},P$。

比较以下三个距离：

$$ \operatorname{dist}(a,b),\quad \operatorname{dist}(a,P),\quad \operatorname{dist}(b,P). $$

第一个最大时保留 $(a,b)$。第二个最大时，设 $p$ 是 $a$ 在 $P$ 上的最近点，返回 $(a,p)$。第三个最大时对称处理。

因为三者中的最大距离一定大于 0，根据上一节引理，选出最远的一对路径后，再替换成它们的最近点即可。

双点 + 双点

合并 $\operatorname{Pair}(a,b)$ 和 $\operatorname{Pair}(c,d)$，相当于维护四个点的最大距离函数。取四点的直径端点即可。

已有的两组内部距离已知，只需额外计算四个跨组距离。

每次合并只进行常数次树上距离或投影查询。

6. 如何求点在路径上的最近点

任意选择原树根，预处理深度和倍增 LCA。

给定点 $x$ 和路径 $[u,v]$，令

$$ \alpha=\operatorname{lca}(x,u),\quad \beta=\operatorname{lca}(x,v),\quad \gamma=\operatorname{lca}(u,v). $$

三者中深度最大的点，就是 $x$ 在路径 $[u,v]$ 上的最近点。它也是三条路径 $x-u,x-v,u-v$ 的公共交点。

点到路径的距离为

$$ \operatorname{dist}(x,[u,v]) =\frac{\operatorname{dist}(x,u)+\operatorname{dist}(x,v)-\operatorname{dist}(u,v)}2 =\mathrm{dep}(x)+\mathrm{dep}(\gamma)-\mathrm{dep}(\alpha)-\mathrm{dep}(\beta). $$

因此，路径状态缓存 $\operatorname{lca}(u,v)$ 后，一次投影只需要再求两次 LCA。

7. 如何求两条路径的交集或最短连接路径

设两条路径为 $A=[a,b]$ 和 $B=[c,d]$。

先把 $a,b$ 分别投影到 $B$，得到 $p,q$。

• 若 $p\ne q$，则两条路径的交集恰好为 $[p,q]$。
• 若 $p=q$，再把 $p$ 投影到 $A$，得到 $r$。若 $r=p$，交集是单点 $p$；否则两条路径不相交，最短连接路径的两端就是 $p,r$。

交集为非退化路径时，两端投影夹住交集；否则整条 $A$ 投影到同一入口，反向投影即可找到另一端。

8. 用线段树处理增删

按照“第几次添加路径”分配叶子编号。

添加一条路径 $u-v$ 时，把对应叶子设为 $\operatorname{Path}(u,v)$；删除第 $id$ 条添加的路径时，把叶子 $id$ 清空。在线段树上向上合并，根节点就精确表示当前全部路径的距离函数。

注意删除编号是添加序号，不是整个操作序列的行号。

根节点为路径状态时，选择交集中的任意点即可，答案为 0。根节点为双点状态 $(a,b)$ 时，答案为

$$ \left\lceil\frac{\operatorname{dist}(a,b)}2\right\rceil. $$

这是因为对任意树点 $x$，$\operatorname{dist}(x,a)+\operatorname{dist}(x,b)\ge\operatorname{dist}(a,b)$，所以最大距离至少为右式。选择 $a-b$ 上靠近中点的一个原树顶点即可达到这个下界。

正确性证明

叶子表示一条路径，三种合并均保持距离函数逐点相等，因此归纳得到根节点精确表示全部有效路径。上述路径状态与双点状态的取值公式分别达到最优下界，故每次输出正确。

复杂度与实现要点

倍增 LCA 预处理时间、空间均为 $O(n\log n)$。单次 LCA 查询为 $O(\log n)$，每次合并只进行常数次 LCA，所以一次更新为 $O(\log m\log n)$。

总时间为 $O(n\log n+m\log m\log n)$，总空间为 $O(n\log n+m)$。遍历原树使用显式序列，避免深链递归。

C++23 实现

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

struct State {
    // kind: 0 = empty, 1 = distance to a path, 2 = maximum distance to two points.
    int kind = 0, a = 0, b = 0, info = 0;
    // info: LCA(a,b) for kind 1; distance(a,b) for kind 2.
};

class Solver {
    int n, levels, base;
    vector<vector<int>> graph, ancestor;
    vector<int> depth;
    vector<State> segment;

    int lca(int u, int v) const {
        if (depth[u] < depth[v]) swap(u, v);
        int gap = depth[u] - depth[v];
        for (int k = 0; gap; ++k, gap >>= 1) if (gap & 1) u = ancestor[k][u];
        if (u == v) return u;
        for (int k = levels - 1; k >= 0; --k) if (ancestor[k][u] != ancestor[k][v]) {
            u = ancestor[k][u];
            v = ancestor[k][v];
        }
        return ancestor[0][u];
    }

    int distance(int u, int v) const {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }

    pair<int, int> project(int x, const State &path) const {
        int p = lca(x, path.a), q = lca(x, path.b), t = path.info;
        int closest = t;
        if (depth[p] > depth[closest]) closest = p;
        if (depth[q] > depth[closest]) closest = q;
        return {closest, depth[x] + depth[t] - depth[p] - depth[q]};
    }

    State merge(State x, State y) const {
        if (!x.kind) return y;
        if (!y.kind) return x;
        if (x.kind == 1 && y.kind == 1) {
            int p = project(x.a, y).first;
            int q = project(x.b, y).first;
            if (p != q) return {1, p, q, lca(p, q)};
            auto [r, d] = project(p, x);
            if (!d) return {1, p, p, p};
            return {2, p, r, d};
        }
        if (x.kind == 1) swap(x, y);
        if (y.kind == 1) {
            State result = x;
            for (int u : {x.a, x.b}) {
                auto [v, d] = project(u, y);
                if (d > result.info) result = {2, u, v, d};
            }
            return result;
        }
        State result = x.info >= y.info ? x : y;
        for (int u : {x.a, x.b}) for (int v : {y.a, y.b}) {
            int d = distance(u, v);
            if (d > result.info) result = {2, u, v, d};
        }
        return result;
    }

public:
    Solver(int vertices, int operations) : n(vertices), levels(1), base(1), graph(n + 1), depth(n + 1) {
        while ((1LL << levels) <= n) ++levels;
        while (base < operations) base <<= 1;
        ancestor.assign(levels, vector<int>(n + 1));
        segment.resize(base * 2);
    }

    void read_tree() {
        for (int i = 1, u, v; i < n; ++i) {
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        vector<int> order{1};
        for (int i = 0; i < n; ++i) {
            int u = order[i];
            for (int v : graph[u]) if (v != ancestor[0][u]) {
                ancestor[0][v] = u;
                depth[v] = depth[u] + 1;
                order.push_back(v);
            }
        }
        for (int k = 1; k < levels; ++k) for (int v = 1; v <= n; ++v) {
            ancestor[k][v] = ancestor[k - 1][ancestor[k - 1][v]];
        }
    }

    void update(int id, int u = 0, int v = 0) {
        int p = base + id - 1;
        segment[p] = u ? State{1, u, v, lca(u, v)} : State{};
        for (p >>= 1; p; p >>= 1) segment[p] = merge(segment[p << 1], segment[p << 1 | 1]);
    }

    int answer() const {
        return segment[1].kind == 2 ? (segment[1].info + 1) / 2 : 0;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    Solver solver(n, m);
    solver.read_tree();
    int inserted = 0;
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            solver.update(++inserted, u, v);
        } else {
            int id;
            cin >> id;
            solver.update(id);
        }
        cout << solver.answer() << '\n';
    }
}