DFS
Contest: Lyft Level 5 Challenge 2018 - Final Round
Difficulty rating: 2700
Tags: data structures

Let $$$T$$$ be a tree on $$$n$$$ vertices. Consider a graph $$$G_0$$$, initially equal to $$$T$$$. You are given a sequence of $$$q$$$ updates, where the $$$i$$$-th update is given as a pair of two distinct integers $$$u_i$$$ and $$$v_i$$$.

For every $$$i$$$ from $$$1$$$ to $$$q$$$, we define the graph $$$G_i$$$ as follows:

- If $$$G_{i-1}$$$ contains an edge $$$\{u_i, v_i\}$$$, then remove this edge to form $$$G_i$$$.
- Otherwise, add this edge to $$$G_{i-1}$$$ to form $$$G_i$$$.

Formally, $$$G_i := G_{i-1} \triangle \{\{u_i, v_i\}\}$$$ where $$$\triangle$$$ denotes the set symmetric difference.

Furthermore, it is guaranteed that $$$T$$$ is always a subgraph of $$$G_i$$$. In other words, an update never removes an edge of $$$T$$$.

Consider a connected graph $$$H$$$ and run a depth-first search on it. One can see that the tree edges (i.e. the edges leading to a not yet visited vertex at the time of traversal) form a spanning tree of the graph $$$H$$$. This spanning tree is not generally fixed for a particular graph — it depends on the starting vertex, and on the order in which the neighbors of each vertex are traversed.

We call vertex $$$w$$$ good if one can order the neighbors of each vertex in such a way that the depth-first search started from $$$w$$$ produces $$$T$$$ as the spanning tree. For every $$$i$$$ from $$$1$$$ to $$$q$$$, find and report the number of good vertices.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \le n \le 2\cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the number of nodes and the number of updates, respectively.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — vertices connected by an edge in $$$T$$$. It is guaranteed that this graph is a tree.

Each of the next $$$q$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — the endpoints of the edge that is added or removed. It is guaranteed that this edge does not belong to $$$T$$$.

Output format:
For each update, print one integer $$$k$$$ — the number of good vertices $$$w$$$ after the corresponding update.

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

Note:
The first sample is depicted in the following figure.

After the first update, $$$G$$$ contains all three possible edges. The result of a DFS is as follows:

- Let the starting vertex be $$$1$$$. We have two choices of ordering the neighbors of $$$1$$$, either $$$[2, 3]$$$ or $$$[3, 2]$$$.   If we choose the former, then we reach vertex $$$2$$$. Regardless of the ordering of its neighbors, the next visited vertex will be $$$3$$$. Thus, the spanning tree generated by this DFS will contain edges $$$\{1, 2\}$$$ and $$$\{2, 3\}$$$, which does not equal to $$$T$$$.  If we choose the latter, we obtain a spanning tree with edges $$$\{1, 3\}$$$ and $$$\{2, 3\}$$$.  Hence, there is no way of ordering the neighbors of vertices such that the DFS produces $$$T$$$, and subsequently $$$1$$$ is not a good vertex.
- Let the starting vertex be $$$2$$$. We have two choices of traversing its neighbors. If we visit $$$3$$$ first, then the spanning tree will consist of edges $$$\{2,3\}$$$ and $$$\{1,3\}$$$, which is not equal to $$$T$$$. If we, however, visit $$$1$$$ first, then we can only continue to $$$3$$$ from here, and the spanning tree will consist of edges $$$\{1, 2\}$$$ and $$$\{1,3\}$$$, which equals to $$$T$$$. Hence, $$$2$$$ is a good vertex.
- The case when we start in the vertex $$$3$$$ is symmetrical to starting in $$$2$$$, and hence $$$3$$$ is a good vertex.

After the second update, the edge between $$$2$$$ and $$$3$$$ is removed, and $$$G = T$$$. It follows that the spanning tree generated by DFS will be always equal to $$$T$$$ independent of the choice of the starting vertex. Thus, the answer is $$$3$$$.

In the second sample, the set of good vertices after the corresponding query is:

- $$$\{2, 3, 5\}$$$
- $$$\{3, 5\}$$$
- $$$\{3, 4, 5\}$$$
- $$$\{4, 5\}$$$
- $$$\{4, 5, 6\}$$$
- $$$\{5, 6\}$$$

Example input:
3 2
1 2
1 3
2 3
3 2

Example output:
2
3

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

Example output:
3
2
3
2
3
2

Editorial:
Let's consider an arbitrary run of DFS producing some tree. Let's root the tree at the starting vertex. It can be shown that on a directed graph, there are only two types of edges. The first are the tree edges (those are the ones that are used to visit a new vertex). The second are edges which, upon being traversed, lead to a vertex that was already visited. It can be shown that, in the rooted tree, those edges always connect a vertex with one of its ancestors.
In other words, all the edges that are dynamically added to the tree must connect a vertex with one of their ancestors. This means that the staring vertex must not lie on the path connecting the two endpoints of such edge, or any of the vertices in some of the subtrees. For instance, on the second sample, the edge $$$\{2,4\}$$$ disallows the vertex $$$1$$$ from being the starting vertex, as it lies on the path from $$$2$$$ to $$$4$$$, and also vertex $$$6$$$.
Each edge thus forbids a certain set of vertices from being the starting point. This yields a straightforward $$$\mathcal O(n^2)$$$ solution. To optimize it further, we can root the tree arbitrarily and renumber the vertices using their DFS visit times. When we do this, we notice that the set of a forbidden vertices for each edge is a union of at most three intervals of vertices. This lets us build an $$$\mathcal O(n \log n)$$$ solution using a segment tree. The operation is add a constant on interval, and then find the minimum on interval and the number of occurrences of said minimum. We add $$$1$$$ to forbid a vertex because of an edge, subtract $$$1$$$ to revert that when the edge is subsequently removed. The answer is the number of minimums on the whole tree if that minimum is $$$0$$$, and $$$0$$$ otherwise.