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 $ 节点的信息。

题目描述

The only difference between this problem and D1 is the bound on the size of the tree. You are given an unrooted tree with $ n $ vertices. There is some hidden vertex $ x $ in that tree that you are trying to find. To do this, you may ask $ k $ queries $ v_1, v_2, \ldots, v_k $ where the $ v_i $ are vertices in the tree. After you are finished asking all of the queries, you are given $ k $ numbers $ d_1, d_2, \ldots, d_k $ , where $ d_i $ is the number of edges on the shortest path between $ v_i $ and $ x $ . Note that you know which distance corresponds to which query. What is the minimum $ k $ such that there exists some queries $ v_1, v_2, \ldots, v_k $ that let you always uniquely identify $ x $ (no matter what $ x $ is). Note that you don't actually need to output these queries.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2\cdot10^5 $ ) — the number of vertices in the tree. Each of the next $ n-1 $ lines contains two integers $ x $ and $ y $ ( $ 1 \le x, y \le n $ ), meaning there is an edges between vertices $ x $ and $ y $ in the tree. It is guaranteed that the given edges form a tree. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

For each test case print a single nonnegative integer, the minimum number of queries you need, on its own line.

输入输出样例

输入样例 #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

说明

In the first test case, there is only one vertex, so you don't need any queries. In the second test case, you can ask a single query about the node $ 1 $ . Then, if $ x = 1 $ , you will get $ 0 $ , otherwise you will get $ 1 $ .

题意翻译

### 题目描述 此问题与[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 $ 节点的信息。