← 返回题目列表

AtCoder · abc447_f

F. 蜈蚣图

中文机器翻译题面 查看原题

分数: 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.