A15067 | Tree Queries (Hard Version)

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.