DFS

题意翻译

题意：给一颗有n个结点的初始树，然后有q次操作，每次操作一对点，如果这对点有边，就删除边（保证不删除初始的树边），否则，就加一条边，接下来你可以从某个点dfs搜索，如果搜索出来的边和初始树的边一样，那这个点就是好的点，求每次操作后有多少个好的点。 输入：先读入n,q，下面n-1行每行两个数x,y表示结点x,结点y之间有一条边，然后q行，每行两个数u,v，表示给结点u,结点v进行一次操作。 输出：q行，每行一个数，第i(1<=i<=q)行表示第i行的好点个数。

题目描述

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](https://en.wikipedia.org/wiki/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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

3 2
1 2
1 3
2 3
3 2

输出样例 #1

2
3

输入样例 #2

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

输出样例 #2

3
2
3
2
3
2

说明

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. Therefore, the answer is $ 2 $ .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\} $