题目详情题解（0）讨论（0）提交记录（0）

CFCF2183D1.Tree Coloring (Easy Version)

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是本题的 Easy 版本，两个版本的区别在于本版本只要求你求出最小操作次数。只有当你解决了所有版本后才能进行 Hack。

给定一棵以 11 号点为根的树 ∗^{\text{∗}}，共 nn 个顶点，编号为 11 到 nn，每个顶点初始都是白色。定义 did_i 为 ii 号顶点到根节点的距离。你可以执行任意次如下操作：

  1. 选择一个白色顶点的子集 SS，满足子集中没有两个节点有边直接连接，且没有两个节点到 11 号节点的距离相等。形式化地说，对于 SS 中任意 x,yx,y 且 x≠yx\ne y，有 dx≠dyd_x\ne d_y，且 xx 和 yy 之间没有边直接连接。
  2. 将 SS 中的所有顶点染成黑色。

你的任务是计算将整棵树染成黑色所需的最小操作次数。∗^{\text{∗}} 一棵树是一个无环连通图。根树是指定某个顶点为根的树。

输入格式

每组测试数据包含若干组测试用例。第一行一个整数 tt（1≤t≤1041\le t\le 10^4），表示测试用例个数。

每组测试用例的第一行为一个整数 nn（2≤n≤2⋅1052\le n\le 2\cdot 10^5），表示树的顶点数。

接下来 n−1n-1 行，每行两个整数 uiu_i 和 viv_i（1≤ui,vi≤n1\le u_i,v_i\le n，ui≠viu_i\ne v_i），表示第 ii 条边的两个端点。

保证所给的边能够构成一棵树。

保证所有测试用例中 nn 的总和不超过 2⋅1052\cdot 10^5。

输出格式

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

输入输出样例

  • 输入#1

    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

    输出#1

    5
4
4
3
3
3
4
4
4
3

说明/提示

在第一个测试用例中，d1=1d_1=1，d2=d3=d4=d5=2d_2=d_3=d_4=d_5=2。我们可以证明至少需要 55 次操作，因为没有两个节点能同时参与一次操作。

在第二个测试用例中，最少需要 44 次操作染黑整棵树。可以将节点 11 和 33 一起染色，剩下的 33 个节点各自单独染色。

首页