题目详情题解（0）讨论（0）提交记录（0）

A60053.最短路

普及+/提高

通过率：0%

时间限制：2.00s

内存限制：128MB

题目描述

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

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

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

输入格式

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

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

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

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

输出格式

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

输入输出样例

  • 输入#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

说明/提示

约束条件

  • 1≤n,m≤5×1051 \leq n, m\leq 5\times 10^5
  • 1≤ui,vi,x,y≤n1 \leq u_i, v_i, x, y \leq n
  • 保证初始输入是一棵树
  • 保证删除操作不会重复删除同一个结点
首页