分数: 500 点
问题陈述
你得到一棵树 T 与 N 顶点编号 1 to N。的 i第一条边连接顶点 A_i 和 B_i.
对于正整数 k,定义一个“长度的蜈蚣图” k“作为图表 3k 通过以下过程获得的顶点:
- 准备一个路径图 k 顶点.
- 对于每个顶点 路径图的 v ,添加两个仅与 v.
例如长度的蜈蚣图 4 如下图所示。

找到最大值 x 这样一个“长度的蜈蚣图” x“作为树的子图包含 T.
Q 给出了测试用例;解决它们中的每一个。
约束
- 1 \le Q
- 3 \le N \le 2 \times 10^5
- 1 \le A_i, B_i \le N
- 给定的图是一棵树。
- 总和 N 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
Q
\text{case}_1
\text{case}_2
\vdots
\text{case}_Q
每个测试用例均按以下格式给出:
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
输出
输出 Q 行。
的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 8 1 3 2 4 2 5 2 6 3 5 4 7 5 8 5 1 5 1 2 1 3 3 4 15 13 3 4 13 11 1 14 9 9 13 13 6 1 10 7 9 13 2 10 5 3 12 15 13 9 10 12 8
示例输出 1
2 1 3
对于第一个测试用例,由六个顶点组成的图 2,3,4,5,6,8 形成“蜈蚣长度图” 2".
无长度蜈蚣图 3 或更多包含作为子图,所以答案是 2。因此,输出 2.