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.


-----Examples-----

Input
3
1
2
1 2
10
2 4
2 1
5 7
3 10
8 6
6 1
1 3
4 7
9 6
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$.

Source: codeforces | Difficulty: HARD
Tags: Graph traversal

Constructive algorithms

Greedy algorithms

Tree algorithms

Dynamic programming


Solutions:
from collections import deque
I = input

def f(x, pre):
	q = deque([(x, pre)])
	dp = [0] * (n + 1)
	R = []
	while q:
		(u, p) = q.popleft()
		R.append(u)
		for v in g[u]:
			if v != p:
				g[v].remove(u)
				q.append((v, u))
	for u in R[::-1]:
		z = c = 0
		for v in g[u]:
			z += dp[v]
			if dp[v] == 0:
				c += 1
			dp[u] = z + max(0, c - 1)
	return dp[x]
for _ in [0] * int(I()):
	n = int(I())
	g = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, I().split())
		g[u].append(v)
		g[v].append(u)
	if n == 1:
		z = 0
	else:
		for u in range(1, n + 1):
			if len(g[u]) >= 3:
				z = f(u, 0)
				break
		else:
			z = 1
	print(z)