AT_abc447_f.[ABC447F] Centipede Graph

给定一棵有 $N$ 个顶点的树 $T$，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

对于一个正整数 $k$，定义“长度为 $k$ 的蜈蚣图”为一个由如下步骤得到的 $3k$ 个顶点的图：

• 先准备一个有 $k$ 个顶点的路径图。
• 对于路径图中的每个顶点 $v$，新增两个只与 $v$ 相邻的新顶点。

例如，下图就是长度为 $4$ 的蜈蚣图。

请你求出一棵树 $T$ 中，能够作为子图包含的“最长蜈蚣图”的长度 $x$ 的最大值。

给出 $Q$ 组测试数据，请分别求解。

输入从标准输入读入，格式如下：

$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

对于第一个测试用例，由顶点 $2,3,4,5,6,8$ 构成的子图就是“长度为 $2$ 的蜈蚣图”。

树中不包含长度为 $3$ 或更长的蜈蚣图，因此答案为 $2$，应输出 $2$。

数据范围

• $1 \le Q$
• $3 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le N$
• 给定的图是一棵树。
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$。
• 所有输入均为整数。

由 ChatGPT 5 翻译