← 返回题目列表

Codeforces · 2063/C

C. 正好删除两个

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

最近,小约翰从他的阿姨那里得到了一棵树来装饰他的房子。但看起来,仅仅一棵树不足以装饰整个房子。小约翰有一个主意。也许他可以从树上删除一些顶点。这会把它变成更多的树!正确的?

给你一棵树$$$^{\text{*}}$$$,有$$$n$$$个顶点。您必须执行以下操作两次。

- 选择一个顶点$$$v$$$;
- 删除与 $$$v$$$ 相关的所有边,以及顶点 $$$v$$$。

请在执行两次操作后找到连接组件的最大数量。

当且仅当存在从 $$$x$$$ 到 $$$y$$$ 的路径时,两个顶点 $$$x$$$ 和 $$$y$$$ 位于同一连通分量中。为了清楚起见,请注意,根据定义,具有 $$$0$$$ 顶点的图具有 $$$0$$$ 连接的组件。$$$^{\text{†}}$$$

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$,表示由边连接的两个顶点 ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$)。保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上输出连接组件的最大数量。

示例

输入 #1

3
2
1 2
4
1 2
2 3
2 4
7
1 2
1 3
2 4
4 5
5 6
5 7

输出 #1

0
2
4

注意

在第一个测试用例中,删除一个顶点两次将使图为空。根据定义,图中具有 $$$0$$$ 顶点的连通分量的数量为 $$$0$$$。因此,答案是$$$0$$$。

在第二个测试用例中,删除两个顶点 $$$1$$$ 和 $$$2$$$ 留下 $$$2$$$ 连接的组件。由于不可能用 $$$2$$$ 顶点创建 $$$3$$$ 连接组件,因此答案是 $$$2$$$。

在第三个测试用例中,删除两个顶点 $$$1$$$ 和 $$$5$$$ 留下 $$$4$$$ 连接组件,它们是 $$$\left\{ 2,4\right\}$$$、$$$\left\{ 3\right\}$$$、$$$\left\{ 6\right\}$$$ 和 $$$\left\{ 7\右\}$$$。可以证明,不可能制作 $$$5$$$ 个连通分量。因此,答案是$$$4$$$。