My Beautiful Madness
Contest: Codeforces Round 692 (Div. 1, based on Technocup 2021 Elimination Round 3)
Difficulty rating: 3500
Tags: data structures, trees

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$$$).

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
1 4
1 1 1
1 1 1
2 1 1
3 0

Example output:
Yes

Example input:
5 3
1 2
1 3
3 4
4 5
1 1 2
1 5 5
3 1

Example output:
No

Editorial:
When I write "a vertex at a distance $$$d$$$ up from the given", I mean such a vertex, if it exists; otherwise the root of the tree.
Let's learn how to answer the query of whether the intersection of $$$d$$$-neighborhoods of all paths is empty. For a given path poman is a vertex at a distance $$$d$$$ up from the LCA of this path.
Lemma: if the intersection is non-empty, then the deepest poman vertex is included in it.
Proof: let the intersection be non-empty, and the deepest poman vertex (let's call it $$$v$$$) is not included in the intersection. The path that spawned $$$v$$$ is located along with the neighborhood in $$$v$$$'s subtree. $$$v$$$ is not included in the intersection, so there is some path whose neighborhood does not contain v. Note that it cannot be in the subtree of $$$v$$$, since then its poman vertex would be deeper than $$$v$$$; hence it lies outside the subtree $$$v$$$ with the neighborhood, hence the intersection of all neighborhoods is empty. Contradiction.
This knowledge allows us to check if the intersection is empty by checking if one particular vertex $$$v$$$ lies in the intersection (for a query, recognizing $$$v$$$ is easy if we maintain a set of LCA of paths from P, ordered by depth). Let $$$kek$$$ be a vertex at a distance $$$d$$$ above $$$v$$$. First, a necessary condition: for each path from $$$P$$$, the subtree of $$$kek$$$ contains at least one end. Let's implement it like this: when the path $$$(u, v)$$$ comes, we do ad[u]++, ad[v]++, ad[LCA(u, v)]--. Now the sum of ad in a subtree of a vertex is the number of ends of different paths in it.
Now we know for sure that there is no path that lies strictly outside the $$$kek$$$ subtree, that is, all paths for which LCA is outside the subtree of $$$kek$$$ pass through $$$kek$$$, and hence $$$v$$$ lies in their $$$d$$$-neighborhood. The only remaining paths to check are those in the $$$kek$$$ subtree. The shortest distance from $$$v$$$ to such paths is the distance to their $$$LCA$$$ (this is not true if the $$$LCA$$$ lies on the path $$$(v, kek)$$$, but this path itself has length $$$d$$$ and we will definitely reach such $$$LCA$$$ from $$$v$$$).
We got the following task about processing queries on a tree:
1. podkek[v]++
2. podkek[v]--
3. among the vertices of the given subtree with $$$podkek[v] > 0$$$, find the farthest from the given vertex (also contained in this subtree)