← 返回题目列表

Codeforces · 2183/D1

D1. 树着色(简单版)

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

这是问题的简单版本。版本之间的区别在于,在这个版本中,您只需要找到最少的操作数。只有解决了该问题的所有版本,您才能破解。

给你一个有根树$$$^{\text{*}}$$$,由$$$n$$$个顶点组成,编号从$$$1$$$到$$$n$$$,其中根的索引为$$$1$$$,每个顶点最初都是白色的。将 $$$d_i$$$ 定义为从根到第 $$$i$$$ 个顶点的距离。您可以多次执行以下操作:

  1. 选择白色顶点的子集 $$$S$$$,使得 $$$S$$$ 中没有两个节点通过边连接,或者到节点 $$$1$$$ 的距离相同。形式上,$$$S$$$ 应该满足所有 $$$x,y\in S$$$ 和 $$$x\neq y$$$、$$$d_x\neq d_y$$$,并且 $$$x$$$ 和 $$$y$$$ 之间没有边。
  2. 将顶点着色为 $$$S$$$ 黑色。
你的工作是找到将整棵树涂成黑色所需的最少操作数。

$$$^{\text{*}}$$$树是没有环的连通图。 有根树是一棵树,其中一个顶点是特殊的,称为根。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) – 树中的顶点数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$, $$$u_i\neq v_i$$$) – 第 $$$i$$$ 边的末端。

保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,在新行中输出最小操作数。

示例

输入
复制

10
5
3 1
1 2
5 1
4 1
5
3 2
2 4
2 5
1 2
5
3 4
4 1
5 1
1 2
5
2 5
3 1
2 1
3 4
5
1 3
1 5
4 3
2 4
13
2 1
3 2
4 2
5 4
6 3
7 1
8 5
9 6
10 4
11 7
12 8
13 10
10
5 7
8 1
1 10
2 8
8 4
9 4
6 1
5 3
7 8
10
7 6
3 7
6 9
7 1
9 8
5 1
3 10
9 2
1 4
10
10 6
2 8
4 10
7 5
1 2
7 10
10 9
9 1
7 3
10
6 8
9 7
4 10
5 9
4 2
3 8
6 5
1 5
1 10

输出
复制

5
4
4
3
3
3
4
4
4
3

注意

在第一个测试用例中,$$$d_1=1$$$ 和 $$$d_2=d_3=d_4=d_5=2$$$。我们可以证明,我们必须执行至少 $$$5$$$ 操作,因为没有两个节点可以同时操作。

在第二个测试用例中,我们可以证明为整个树着色所需的最少操作数为 $$$4$$$。一种方法是在同一操作中为节点 $$$1$$$ 和 $$$3$$$ 着色,并在其自己的操作中为所有 $$$3$$$ 其他节点着色。