2026牛客暑期多校 8——Problem F. Tree Shifts Her

题目大意

时间限制：C/C++/Rust/Pascal 4 秒，其他语言 8 秒
空间限制：C/C++/Rust/Pascal 1024 MB，其他语言 2048 MB
Special Judge，64bit IO Format: %lld

在月球上，篝一直研究着一份浩繁的可能性集合。她用一种极度压缩的语言讲述自己的发现：寥寥数语所承载的信息，就足以压垮一个普通人的心智。

孝太郎不愿认输，一次次动用自己加速思维的能力去追赶她的讲解。这样的尝试失败了太多次，于是篝决定在继续讲下去之前，先测一测他的反应速度。当然，"把话说得简单些"从来不在她的选项之内。

这一次，篝取出了一棵有 $n$ 个顶点的世界树，顶点编号为 $1$ 到 $n$ 。这棵树是无向、无权的。

每次询问给出两个顶点 $u$ 和 $v$ 。篝会暂时删去 $u$ 到 $v$ 的唯一简单路径上的所有边，此时世界树会分裂成若干个连通块，构成一个森林。

一个连通块的直径定义为其中任意两点之间距离的最大值，其中距离指两点间路径上的边数。特别地，只含一个顶点的连通块，其直径为 $0$ 。

对于每次询问，孝太郎需要求出所有连通块直径之和。

各次询问相互独立：每次询问结束后，所有被删去的边都会恢复原状，然后才进行下一次询问。特别地，若 $u = v$ ，则该路径上不含任何边，世界树保持不变。

第一行包含两个整数 $n$ 和 $q$ （ $1 \le n, q \le 2 \cdot 10^5$ ）。

接下来 $n - 1$ 行，每行两个整数 $a_i$ 和 $b_i$ （ $1 \le a_i, b_i \le n$ ），表示顶点 $a_i$ 与 $b_i$ 之间有一条无向边。保证这些边构成一棵树。

接下来 $q$ 行，每行两个整数 $u_i$ 和 $v_i$ （ $1 \le u_i, v_i \le n$ ），表示一次询问。

对于每次询问，输出一行一个整数，表示删去对应路径上的边之后，所有连通块的直径之和。

样例中的树形态如下：边集为 $\{(1,2),(2,3),(3,4),(3,5),(5,6),(5,7)\}$ 。

询问 $1$ ： $u = 1, v = 4$ 。路径为 $1 \to 2 \to 3 \to 4$ ，删去边 $(1,2),(2,3),(3,4)$ 。剩余连通块为 $\{1\}$ 、 $\{2\}$ 、 $\{4\}$ 、 $\{3,5,6,7\}$ ，直径分别为 $0, 0, 0, 2$ ，总和为 $2$ 。
询问 $2$ ： $u = 6, v = 7$ 。路径为 $6 \to 5 \to 7$ ，删去边 $(5,6),(5,7)$ 。剩余连通块为 $\{6\}$ 、 $\{7\}$ 、 $\{1,2,3,4,5\}$ ，直径分别为 $0, 0, 3$ （如 $1$ 与 $4$ 之间），总和为 $3$ 。
询问 $3$ ： $u = 3, v = 3$ 。路径不含任何边，整棵树保持不变，其直径为 $4$ （如 $1$ 与 $6$ 之间），总和为 $4$ 。
询问 $4$ ： $u = 2, v = 5$ 。路径为 $2 \to 3 \to 5$ ，删去边 $(2,3),(3,5)$ 。剩余连通块为 $\{1,2\}$ 、 $\{3,4\}$ 、 $\{5,6,7\}$ ，直径分别为 $1, 1, 2$ ，总和为 $4$ 。
询问 $5$ ： $u = 1, v = 7$ 。路径为 $1 \to 2 \to 3 \to 5 \to 7$ ，删去边 $(1,2),(2,3),(3,5),(5,7)$ 。剩余连通块为 $\{1\}$ 、 $\{2\}$ 、 $\{3,4\}$ 、 $\{5,6\}$ 、 $\{7\}$ ，直径分别为 $0, 0, 1, 1, 0$ ，总和为 $2$ 。

源代码