← 返回题目列表

Codeforces · 1695/D2

D2. 树查询(硬版)

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

这个问题和 D1 之间的唯一区别是树大小的限制。

给你一棵有 $$$n$$$ 个顶点的无根树。您正在尝试查找该树中的一些隐藏顶点 $$$x$$$。

为此,您可以要求 $$$k$$$ 查询 $$$v_1, v_2, \ldots, v_k$$$,其中 $$$v_i$$$ 是树中的顶点。询问完所有查询后,您将获得 $$$k$$$ 数字 $$$d_1、d_2、\ldots、d_k$$$,其中 $$$d_i$$$ 是 $$$v_i$$$ 和 $$$x$$$ 之间最短路径上的边数。请注意,您知道哪个距离对应于哪个查询。

最小 $$$k$$$ 是多少,这样存在一些查询 $$$v_1, v_2, \ldots, v_k$$$ 让您始终唯一地标识 $$$x$$$(无论 $$$x$$$ 是什么)。

请注意,您实际上不需要输出这些查询。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 树中的顶点数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$),这意味着树中的顶点 $$$x$$$ 和 $$$y$$$ 之间有一条边。

保证给定的边形成一棵树。

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

输出

对于每个测试用例,在其自己的行上打印一个非负整数,即您需要的最小查询数。

示例

输入 #1

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

输出 #1

0
1
2

注意

在第一个测试用例中,只有一个顶点,因此您不需要任何查询。

在第二个测试用例中,您可以询问有关节点 $$$1$$$ 的单个查询。那么,如果$$$x = 1$$$,你将得到$$$0$$$,否则你将得到$$$1$$$。