CF2183D1 Tree Coloring (Easy Version)

这是本题的 Easy 版本，两个版本的区别在于本版本只要求你求出最小操作次数。只有当你解决了所有版本后才能进行 Hack。 给定一棵以 $1$ 号点为根的树 $^{\text{∗}}$，共 $n$ 个顶点，编号为 $1$ 到 $n$，每个顶点初始都是白色。定义 $d_i$ 为 $i$ 号顶点到根节点的距离。你可以执行任意次如下操作： 1. 选择一个白色顶点的子集 $S$，满足子集中没有两个节点有边直接连接，且没有两个节点到 $1$ 号节点的距离相等。形式化地说，对于 $S$ 中任意 $x,y$ 且 $x\ne y$，有 $d_x\ne 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\ne v_i$），表示第 $i$ 条边的两个端点。 保证所给的边能够构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每组测试用例，输出最小的操作次数，每组一行。

在第一个测试用例中，$d_1=1$，$d_2=d_3=d_4=d_5=2$。我们可以证明至少需要 $5$ 次操作，因为没有两个节点能同时参与一次操作。 在第二个测试用例中，最少需要 $4$ 次操作染黑整棵树。可以将节点 $1$ 和 $3$ 一起染色，剩下的 $3$ 个节点各自单独染色。 由 ChatGPT 5 翻译