← 返回题目列表

Codeforces · 1238/F

F. 最大子树

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

假设您有 $$$k$$$ 一维线段 $$$s_1, s_2, \dots s_k$$$ (每个线段由两个整数表示 - 它的端点)。然后您可以在这些段上构建以下图表。该图由 $$$k$$$ 个顶点组成,当且仅当线段 $$$s_i$$$ 和 $$$s_j$$$ 相交(存在至少一个属于它们两者的点)时,第 $$$i$$$ 和第 $$$j$$$ 顶点之间存在一条边 ($$$i \neq j$$$)。

例如,如果 $$$s_1 = [1, 6]、s_2 = [8, 20]、s_3 = [4, 10]、s_4 = [2, 13]、s_5 = [17, 18]$$$,则结果图如下:

如果可以选择 $$$m$$$ 一维线段,使得在这些线段上构建的图与该树一致,则大小为 $$$m$$$ 的树是好的。

给你一棵树,你必须找到其最大可能大小的好子树。回想一下,子树是树的连通子图。

请注意,您必须回答 $$$q$$$ 独立查询。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 15 \cdot 10^4$$$) — 查询的数量。

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

接下来的 $$$n - 1$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$) 表示顶点 $$$x$$$ 和 $$$y$$$ 之间的边。保证给定的图是一棵树。

保证所有$$$n$$$的总和不超过$$$3 \cdot 10^5$$$。

输出

对于每个查询,打印一个整数 — 给定树的好子树的最大大小。

示例

输入 #1

1
10
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10

输出 #1

8

注意

在第一个查询中,有一个大小为 $$$8$$$ 的良好子树。属于该子树的顶点是$$${9, 4, 10, 2, 5, 1, 6, 3}$$$。