← 返回比赛
已结束 GESP巅峰赛#23
← 上一题 下一题 →

A5089 | 最短路

时间限制2s
内存限制128MB
通过 / 提交0/0

题目描述

$Alice$ 最近学习了图论中的最短路算法，现在她遇到了一个关于树操作的有趣问题。$Bob$ 拥有一棵包含 $n$ 个节点的树结构，其中每条边的长度都是 $1$。$Bob$ 可以对这棵树执行以下两种操作：

- 操作 1 x（节点删除操作）：删除树中的节点 $x$ ，保证结点 $x$ 之前没有被删除 。假设与 $x$ 直接相连的节点集合为 $\{v_1, v_2, \dots, v_k\}$，那么在删除 $x$ 后，系统会自动在这些相邻节点之间两两建立新的边，且每条新边的长度仍保持为 $1$。
- 操作 2 x y（最短路径查询）：查询节点 $x$ 和 $y$ 之间的最短路径长度（保证在执行查询时 $x$ 和 $y$ 都未被删除）。

现在，Bob 将要依次执行 $m$ 次上述操作，Alice 需要设计一个高效的算法来处理这些操作并正确回答所有的查询请求。你能帮助她解决这个具有挑战性的问题吗？

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示初始树的结点数和操作次数。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示初始树上结点 $u_i$ 和 $v_i$ 之间存在一条边。

最后 $m$ 行，每行描述一个操作：

- 若输入为 1 x，表示删除结点 $x$（保证 $x$ 未被删除过）。
- 若输入为 2 x y，表示查询结点 $x$ 和 $y$ 之间的最短路径长度（保证 $x$ 和 $y$ 未被删除）。

输出格式

对于每个 2 x y 操作，输出一行一个整数，表示 $x$ 和 $y$ 之间的最短路径长度。

输入输出样例

输入 #1
5 4
2 1
2 3
1 4
1 5
2 1 2
1 1
1 2
2 3 4
输出 #1
1
1
输入 #2
10 30
2 1
3 2
4 3
5 3
6 5
7 3
8 5
9 6
10 5
2 9 10
2 5 1
2 4 4
2 8 4
2 5 8
2 6 5
2 10 5
2 1 2
2 7 4
2 8 7
2 4 10
2 1 5
2 10 3
2 9 3
2 10 8
2 7 4
2 2 9
2 7 1
2 8 10
2 1 3
2 6 4
2 5 3
2 4 6
2 7 8
2 3 5
2 1 8
2 7 3
2 5 5
2 3 5
2 3 2
输出 #2
3
3
0
3
1
1
1
1
2
3
3
3
2
3
2
2
4
3
2
2
3
1
3
3
1
4
1
0
1
1
C++ 编辑器
输入
输出