2026牛客暑期多校 8——Problem F. Tree Shifts Her · znzryb
## 题目大意
### 世界树的裂隙
时间限制:C/C++/Rust/Pascal 4 秒,其他语言 8 秒
空间限制:C/C++/Rust/Pascal 1024 MB,其他语言 2048 MB
Special Judge,64bit IO Format: `%lld`
<!-- Notion block type: heading_4 -->
在月球上,篝一直研究着一份浩繁的可能性集合。她用一种极度压缩的语言讲述自己的发现:寥寥数语所承载的信息,就足以压垮一个普通人的心智。
孝太郎不愿认输,一次次动用自己加速思维的能力去追赶她的讲解。这样的尝试失败了太多次,于是篝决定在继续讲下去之前,先测一测他的反应速度。当然,"把话说得简单些"从来不在她的选项之内。
这一次,篝取出了一棵有 $n$ 个顶点的**世界树**,顶点编号为 $1$ 到 $n$。这棵树是无向、无权的。
每次询问给出两个顶点 $u$ 和 $v$。篝会暂时删去 $u$ 到 $v$ 的唯一简单路径上的**所有边**,此时世界树会分裂成若干个连通块,构成一个森林。
一个连通块的**直径**定义为其中任意两点之间距离的最大值,其中距离指两点间路径上的边数。特别地,只含一个顶点的连通块,其直径为 $0$。
对于每次询问,孝太郎需要求出**所有连通块直径之和**。
各次询问相互**独立**:每次询问结束后,所有被删去的边都会恢复原状,然后才进行下一次询问。特别地,若 $u = v$,则该路径上不含任何边,世界树保持不变。
<!-- Notion block type: heading_4 -->
第一行包含两个整数 $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$),表示一次询问。
<!-- Notion block type: heading_4 -->
对于每次询问,输出一行一个整数,表示删去对应路径上的边之后,所有连通块的直径之和。
<!-- Notion block type: heading_4 -->
<!-- Notion block type: heading_4 -->
```
7 5
1 2
2 3
3 4
3 5
5 6
5 7
1 4
6 7
3 3
2 5
1 7
```
<!-- Notion block type: heading_4 -->
```
2
3
4
4
2
```
<!-- Notion block type: heading_4 -->



样例中的树形态如下:边集为 $\{(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$。
## 思路讲解
## AC代码
::: 源代码
```cpp
```
:::
## 心路历程(WA,TLE,MLE……)