My Beautiful Madness

题意翻译

给定一颗大小为$n(n\le2*10^5)$的树，$m(m\le2*10^5)$次操作，维护一个初始为空的路径集合$P$。 定义树上一条路径的$d$邻居（一个点集）$S$为：$x \in S$当前仅当存在一个路径上的点$y$满足$dis(x,y)\le d$。 操作分为三种： $1.$输入$u,v$，在$P$中加入$u$到$v$的路径。 $2.$输入$u,v$，删除$P$中**一个**$u$到$v$的路径。 （注意$u$到$v$的路径与$v$到$u$的路径是相同的，若有多个$u$到$v$的路径只删除一个） $3.$输入$d$，询问$P$中所有路径的$d$邻居交集是否为空，若不为空输出Yes，否则输出No。

题目描述

You are given a tree. We will consider simple paths on it. Let's denote path between vertices $ a $ and $ b $ as $ (a, b) $ . Let $ d $ -neighborhood of a path be a set of vertices of the tree located at a distance $ \leq d $ from at least one vertex of the path (for example, $ 0 $ -neighborhood of a path is a path itself). Let $ P $ be a multiset of the tree paths. Initially, it is empty. You are asked to maintain the following queries: - $ 1 $ $ u $ $ v $ — add path $ (u, v) $ into $ P $ ( $ 1 \leq u, v \leq n $ ). - $ 2 $ $ u $ $ v $ — delete path $ (u, v) $ from $ P $ ( $ 1 \leq u, v \leq n $ ). Notice that $ (u, v) $ equals to $ (v, u) $ . For example, if $ P = \{(1, 2), (1, 2)\} $ , than after query $ 2 $ $ 2 $ $ 1 $ , $ P = \{(1, 2)\} $ . - $ 3 $ $ d $ — if intersection of all $ d $ -neighborhoods of paths from $ P $ is not empty output "Yes", otherwise output "No" ( $ 0 \leq d \leq n - 1 $ ).

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ — the number of vertices in the tree and the number of queries, accordingly ( $ 1 \leq n \leq 2 \cdot 10^5 $ , $ 2 \leq q \leq 2 \cdot 10^5 $ ). Each of the following $ n - 1 $ lines contains two integers $ x_i $ and $ y_i $ — indices of vertices connected by $ i $ -th edge ( $ 1 \le x_i, y_i \le n $ ). The following $ q $ lines contain queries in the format described in the statement. It's guaranteed that: - for a query $ 2 $ $ u $ $ v $ , path $ (u, v) $ (or $ (v, u) $ ) is present in $ P $ , - for a query $ 3 $ $ d $ , $ P \neq \varnothing $ , - there is at least one query of the third type.

输出格式

For each query of the third type output answer on a new line.

输入输出样例

输入样例 #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