CF1695D2 Tree Queries (Hard Version)

此问题与[CF1695D1 Tree Queries (Easy Version)](https://www.luogu.com.cn/problem/CF1695D1)的唯一区别是树的大小的限定。 给定一棵无根树，有 $ n $ 个顶点。在这棵树上有一个顶点 $ x $ ,你希望找到它。 要找到 $ 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 1e4 $ )。 对于每组数据的描述如下。 每组数据的第一行包含一个整数 $ n $ ( $ 1 \le n \le 2e5 $ ) 即树中的顶点数。 然后有 $ n - 1 $ 行,每行包含两个整数 $ x $ 和 $ y $ ( $ 1 \le x, y \le n $ )，意味着树中顶点 $ x $ 和 $ y $ 之间有一条边。 数据保证所给的边一定形成一棵树。 数据保证每个测试点中 $ n $ 的总和不超过 $ 2e5 $ 。

对于每组数据，在此行输出一个非负整数，即为你需要的最小查询数。(即每一行对应输出一个查询数字) ### 输入输出样例 #### 样例输入 #1 ```plain 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 ```plain 0 1 2 ```

在第一组数据中，只有一个顶点，因此不需要任何查询。 在第二组数据中，你可以进行关于节点 $ 1 $ 的单个查询从而得到 $ x $ 节点的信息。