Tree Queries (Hard Version)

2000ms

262144K

Description:

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.

Input:

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$$$.

Output:

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

Sample Input:

Sample Output:

0
1
2

Note:

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$$$.

Informação

Provedor Codeforces

Código CF1695D2