这是问题的简单版本。版本之间的区别在于,在这个版本中,您只需要找到最少的操作数。只有解决了该问题的所有版本,您才能破解。
给你一个有根树$$$^{\text{*}}$$$,由$$$n$$$个顶点组成,编号从$$$1$$$到$$$n$$$,其中根的索引为$$$1$$$,每个顶点最初都是白色的。将 $$$d_i$$$ 定义为从根到第 $$$i$$$ 个顶点的距离。您可以多次执行以下操作:
- 选择白色顶点的子集 $$$S$$$,使得 $$$S$$$ 中没有两个节点通过边连接,或者到节点 $$$1$$$ 的距离相同。形式上,$$$S$$$ 应该满足所有 $$$x,y\in S$$$ 和 $$$x\neq y$$$、$$$d_x\neq d_y$$$,并且 $$$x$$$ 和 $$$y$$$ 之间没有边。
- 将顶点着色为 $$$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$$$。
输出
对于每个测试用例,在新行中输出最小操作数。
示例
输入复制
1053 11 25 14 153 22 42 51 253 44 15 11 252 53 12 13 451 31 54 32 4132 13 24 25 46 37 18 59 610 411 712 813 10105 78 11 102 88 49 46 15 37 8107 63 76 97 19 85 13 109 21 41010 62 84 107 51 27 1010 99 17 3106 89 74 105 94 23 86 51 51 10
输出复制
5443334443
注意
在第一个测试用例中,$$$d_1=1$$$ 和 $$$d_2=d_3=d_4=d_5=2$$$。我们可以证明,我们必须执行至少 $$$5$$$ 操作,因为没有两个节点可以同时操作。
在第二个测试用例中,我们可以证明为整个树着色所需的最少操作数为 $$$4$$$。一种方法是在同一操作中为节点 $$$1$$$ 和 $$$3$$$ 着色,并在其自己的操作中为所有 $$$3$$$ 其他节点着色。