← 返回题目列表

Codeforces · 1464/F

F. 我美丽的疯狂

中文机器翻译题面 查看原题

你得到一棵树。我们将考虑其上的简单路径。我们将顶点 $$$a$$$ 和 $$$b$$$ 之间的路径表示为 $$$(a, b)$$$。令 $$$d$$$-路径的邻域为距路径的至少一个顶点 $$$\leq d$$$ 距离的树的一组顶点(例如,$$$0$$$-路径的邻域是路径本身)。令 $$$P$$$ 为树路径的多重集。最初,它是空的。您需要保留以下查询:

- $$$1$$$ $$$u$$$ $$$v$$$ — 将路径 $$$(u, v)$$$ 添加到 $$$P$$$ ($$$1 \leq u, v \leq n$$$)。
- $$$2$$$ $$$u$$$ $$$v$$$ — 从 $$$P$$$ 中删除路径 $$$(u, v)$$$ ($$$1 \leq u, v \leq n$$$)。请注意 $$$(u, v)$$$ 等于 $$$(v, u)$$$。例如,如果 $$$P = \{(1, 2), (1, 2)\}$$$,则在查询 $$$2$$$ $$$2$$$ $$$1$$$ 之后,$$$P = \{(1, 2)\}$$$。
- $$$3$$$ $$$d$$$ — 如果来自 $$$P$$$ 的路径的所有 $$$d$$$-邻域的交集不为空,则输出“Yes”,否则输出“No”($$$0 \leq d \leq n - 1$$$)。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ - 树中的顶点数和查询数($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$2 \leq q \leq 2 \cdot 10^5$$$)。

以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ - 由 $$$i$$$ 边连接的顶点索引 ($$$1 \le x_i, y_i \le n$$$)。

以下 $$$q$$$ 行包含语句中描述的格式的查询。

保证:

- 对于查询 $$$2$$$ $$$u$$$ $$$v$$$,路径 $$$(u, v)$$$ (或 $$$(v, u)$$$)存在于 $$$P$$$ 中,
- 对于查询 $$$3$$$ $$$d$$$, $$$P \neq \varnothing$$$,
- 至少有一个第三类型的查询。

输出

对于第三种类型的每个查询,在新行上输出答案。

示例

输入 #1

1 4
1 1 1
1 1 1
2 1 1
3 0

输出 #1

Yes

输入 #2

5 3
1 2
1 3
3 4
4 5
1 1 2
1 5 5
3 1

输出 #2

No

输入 #3

10 6
1 2
2 3
3 4
4 7
7 10
2 5
5 6
6 8
8 9
1 9 9
1 9 8
1 8 5
3 0
3 1
3 2

输出 #3

No
Yes
Yes