Colored Subgraphs

题意翻译

Alice有一棵 $n$ 个节点的树。 他要选择一个节点 $r$，然后： - 设一个数组 $d$，$d_i$ 表示 $r$ 点到 $i$ 点的距离。 - 并把所有节点都染个色。 但染色必须要满足两个条件： - 对于任意被染了相同颜色的点对 $(x,y)$，从点 $x$ 到点 $y$ 的路径上所有点（包括点 $x$ 和点 $y$）的颜色都一样。 - 对于任意被染了相同颜色的点对 $(x,y)$，条件 $d_x \not= d_y$ 必须都满足。 现在，定义一个染色方案的代价为一种颜色的最小出现次数，即 $\min(\text{cnt}_i)$。 现在，他让你选择一个最优的节点 $r$，使得染色方案的最小代价最大。

题目描述

Monocarp has a tree, consisting of $ n $ vertices. He is going to select some vertex $ r $ and perform the following operations on each vertex $ v $ from $ 1 $ to $ n $ : - set $ d_v $ equal to the distance from $ v $ to $ r $ (the number of edges on the shortest path); - color $ v $ some color. A nice coloring satisfies two conditions: - for each pair of vertices of the same color $ (v, u) $ , there exists a path from $ v $ to $ u $ that only visits vertices of the same color; - for each pair of vertices of the same color $ (v, u) $ , $ d_v \neq d_u $ . Note that Monocarp can choose any amount of different colors he wants to use. For each used color, he then counts the number of vertices of this color. The cost of the tree is the minimum of these numbers. What can be the maximum cost of the tree?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree. Each of the next $ n-1 $ lines contains two integers $ v $ and $ u $ ( $ 1 \le v, u \le n $ ) — the description of an edge. The given edges form a tree. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each testcase print a single integer — the maximum possible cost of the tree.

输入输出样例

输入样例 #1

4
4
1 2
2 3
3 4
5
1 2
1 3
1 4
1 5
3
1 3
3 2
7
3 2
2 5
7 5
3 1
1 6
1 4

输出样例 #1

4
1
3
3

**题意翻译**

爱丽丝有一棵有 $ n $ 个节点的树。

他要选择一个节点 $ r $，然后：

- 设一个数组 $ d $，$ d_i $ 表示 $ r $ 点到 $ i $ 点的距离。
- 并把所有节点都染个色。

但染色必须要满足两个条件：

- 对于任意被染了相同颜色的点对 $ (x,y) $，从点 $ x $ 到点 $ y $ 的路径上所有点（包括点 $ x $ 和点 $ y $）的颜色都一样。
- 对于任意被染了相同颜色的点对 $ (x,y) $，条件 $ d_x \neq d_y $ 必须都满足。

现在，定义一个染色方案的代价为一种颜色的最小出现次数，即 $ \min(\text{cnt}_i) $。

现在，他让你选择一个最优的节点 $ r $，使得染色方案的最小代价最大。

**题目描述**

Monocarp有一棵包含 $ n $ 个顶点的树。

他打算选择一个顶点 $ r $ 并对每个顶点 $ v $ 从 1 到 $ n $ 执行以下操作：

- 将 $ d_v $ 设置为从 $ v $ 到 $ r $ 的距离（最短路径上的边数）；
- 将 $ v $ 染成某种颜色。

一个好的染色满足两个条件：

- 对于每一对同色的顶点 $ (v, u) $，存在一条从 $ v $ 到 $ u $ 的路径，该路径只访问同色的顶点；
- 对于每一对同色的顶点 $ (v, u) $，$ d_v \neq d_u $。

注意 Monocarp 可以选择任意数量的不同颜色来使用。

对于每种使用的颜色，他然后计算这种颜色的顶点数。树的成本是这些数字的最小值。

树的最高成本可以是什么？

**输入输出格式**

**输入格式**

第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) — 测试用例的数量。

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

接下来的 $ n-1 $ 行每行包含两个整数 $ v $ 和 $ u $ ( $ 1 \le v, u \le n $ ) — 边的描述。

给出的边构成一棵树。所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。

**输出格式**

对于每个测试用例，打印一个整数 — 树的最大可能成本。**题意翻译** 爱丽丝有一棵有 $ n $ 个节点的树。 他要选择一个节点 $ r $，然后： - 设一个数组 $ d $，$ d_i $ 表示 $ r $ 点到 $ i $ 点的距离。 - 并把所有节点都染个色。 但染色必须要满足两个条件： - 对于任意被染了相同颜色的点对 $ (x,y) $，从点 $ x $ 到点 $ y $ 的路径上所有点（包括点 $ x $ 和点 $ y $）的颜色都一样。 - 对于任意被染了相同颜色的点对 $ (x,y) $，条件 $ d_x \neq d_y $ 必须都满足。 现在，定义一个染色方案的代价为一种颜色的最小出现次数，即 $ \min(\text{cnt}_i) $。 现在，他让你选择一个最优的节点 $ r $，使得染色方案的最小代价最大。 **题目描述** Monocarp有一棵包含 $ n $ 个顶点的树。 他打算选择一个顶点 $ r $ 并对每个顶点 $ v $ 从 1 到 $ n $ 执行以下操作： - 将 $ d_v $ 设置为从 $ v $ 到 $ r $ 的距离（最短路径上的边数）； - 将 $ v $ 染成某种颜色。 一个好的染色满足两个条件： - 对于每一对同色的顶点 $ (v, u) $，存在一条从 $ v $ 到 $ u $ 的路径，该路径只访问同色的顶点； - 对于每一对同色的顶点 $ (v, u) $，$ d_v \neq d_u $。 注意 Monocarp 可以选择任意数量的不同颜色来使用。 对于每种使用的颜色，他然后计算这种颜色的顶点数。树的成本是这些数字的最小值。 树的最高成本可以是什么？ **输入输出格式** **输入格式** 第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) — 测试用例的数量。 每个测试用例的第一行包含一个整数 $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — 树中顶点的数量。 接下来的 $ n-1 $ 行每行包含两个整数 $ v $ 和 $ u $ ( $ 1 \le v, u \le n $ ) — 边的描述。 给出的边构成一棵树。所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试用例，打印一个整数 — 树的最大可能成本。