[Solution] Tree Queries (Hard Version) Codeforces Solution

[Solution] Tree Queries (Hard Version) Codeforces Solution

D2. Tree Queries (Hard Version)

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

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 v1,v2,…,vk where the vi are vertices in the tree. After you are finished asking all of the queries, you are given k numbers d1,d2,…,dk, where di is the number of edges on the shortest path between vi and x. Note that you know which distance corresponds to which query.

What is the minimum k such that there exists some queries v1,v2,…,vk that let you always uniquely identify x (no matter what x is).

Solution Click Below:-  CLICK HERE

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≤t≤104). Description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤2⋅105)  — the number of vertices in the tree.

Each of the next n−1 lines contains two integers x and y (1≤x,y≤n), meaning there is an edges between vertices x and y in the tree.

It is guaranteed that the given edges form a tree.

Subrectangle Guess Codeforces Solution

Circle Game Codeforces Solution

Zero Path Codeforces Solution

Tree Queries (Easy Version) Codeforces Solution

Tree Queries (Hard Version) Codeforces Solution

Ambiguous Dominoes Codeforces Solution

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

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