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 翻译