← 返回题目列表

Codeforces · 1044/F

F. 深度优先搜索

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

设 $$$T$$$ 是 $$$n$$$ 个顶点上的树。考虑一个图$$$G_0$$$,最初等于$$$T$$$。您将获得一系列 $$$q$$$ 更新,其中第 $$$i$$$ 更新作为一对两个不同的整数 $$$u_i$$$ 和 $$$v_i$$$ 给出。

对于从 $$$1$$$ 到 $$$q$$$ 的每个 $$$i$$$,我们定义图 $$$G_i$$$ 如下:

- 如果 $$$G_{i-1}$$$ 包含边 $$$\{u_i, v_i\}$$$,则删除该边以形成 $$$G_i$$$。
- 否则,将此边添加到 $$$G_{i-1}$$$ 以形成 $$$G_i$$$。

形式上, $$$G_i := G_{i-1} \triangle \{\{u_i, v_i\}\}$$$ 其中 $$$\triangle$$$ 表示集合对称差。

此外,保证 $$$T$$$ 始终是 $$$G_i$$$ 的子图。换句话说,更新永远不会删除 $$$T$$$ 的边。

考虑一个连通图 $$$H$$$ 并对其运行深度优先搜索。可以看到,树边(即遍历时通向尚未访问的顶点的边)形成了图 $$$H$$$ 的生成树。对于特定图,该生成树通常不是固定的 - 它取决于起始顶点以及遍历每个顶点的邻居的顺序。

如果能够以这样一种方式对每个顶点的邻居进行排序,使得从 $$$w$$$ 开始的深度优先搜索产生 $$$T$$$ 作为生成树,那么我们称顶点 $$$w$$$ 是好的。对于从 $$$1$$$ 到 $$$q$$$ 的每个 $$$i$$$,查找并报告良好顶点的数量。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$3 \le n \le 2\cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$)——分别是节点数和更新数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — 由 $$$T$$$ 中的边连接的顶点。保证这个图是一棵树。

接下来的 $$$q$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) - 添加或删除的边的端点。保证这条边不属于$$$T$$$。

输出

对于每次更新,打印一个整数 $$$k$$$ — 相应更新后的好顶点 $$$w$$$ 的数量。

示例

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

注意

第一个示例如下图所示。

第一次更新后,$$$G$$$ 包含所有三个可能的边。 DFS的结果如下:

- 令起始顶点为$$$1$$$。我们有两种选择对 $$$1$$$ 的邻居进行排序,即 $$$[2, 3]$$$ 或 $$$[3, 2]$$$。 如果我们选择前者,那么我们到达顶点$$$2$$$。无论其邻居的顺序如何,下一个访问的顶点都将是 $$$3$$$。因此,此 DFS 生成的生成树将包含边 $$$\{1, 2\}$$$ 和 $$$\{2, 3\}$$$,其不等于 $$$T$$$。 如果我们选择后者,我们将获得一个边为 $$$\{1, 3\}$$$ 和 $$$\{2, 3\}$$$ 的生成树。 因此,无法对顶点的邻居进行排序,使得 DFS 生成 $$$T$$$,因此 $$$1$$$ 不是一个好的顶点。
- 令起始顶点为$$$2$$$。我们有两种遍历其邻居的选择。如果我们先访问$$$3$$$,那么生成树将由边$$$\{2,3\}$$$和$$$\{1,3\}$$$组成,它不等于$$$T$$$。然而,如果我们先访问$$$1$$$,那么我们只能从这里继续到$$$3$$$,生成树将由边$$$\{1, 2\}$$$和$$$\{1,3\}$$$组成,等于$$$T$$$。因此,$$$2$$$ 是一个好的顶点。
- 当我们从顶点 $$$3$$$ 开始的情况与从 $$$2$$$ 开始对称,因此 $$$3$$$ 是一个好的顶点。

第二次更新后,$$$2$$$ 和 $$$3$$$ 之间的边被删除,$$$G = T$$$。由此可见,DFS 生成的生成树将始终等于 $$$T$$$,与起始顶点的选择无关。因此,答案是$$$3$$$。

在第二个示例中,相应查询后的好顶点集合为:

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