Tree Queries (Hard Version) (Codeforces 1695D2)
Tags: Greedy, trees

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.

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

Sample Inputs:
3
1
2
1 2
10
2 4
2 1
5 7
3 10
8 6
6 1
1 3
4 7
9 6

Sample Outputs:
0
1
2

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)