Distance Tree (hard version) solution codeforces- This version of the problem differs from the previous one only in the constraint on nn. A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The distance between two vertices is the minimum sum of weights on the path connecting them.

Distance Tree (hard version) solution codeforces

 

This version of the problem differs from the previous one only in the constraint on nn.

A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The distance between two vertices is the minimum sum of weights on the path connecting them.

You are given a weighted tree with nn vertices, each edge has a weight of 11. Denote d(v)d(v) as the distance between vertex 11 and vertex vv.

Let f(x)f(x) be the minimum possible value of max1vn d(v)max1≤v≤n d(v) if you can temporarily add an edge with weight xx between any two vertices aa and bb (1a,bn)(1≤a,b≤n). Note that after this operation, the graph is no longer a tree.

For each integer xx from 11 to nn, find f(x)f(x).

Input Distance Tree (hard version) solution codeforces

The first line contains a single integer tt (1t1041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer nn (2n31052≤n≤3⋅105).

Each of the next n1n−1 lines contains two integers uu and vv (1u,vn1≤u,v≤n) indicating that there is an edge between vertices uu and vv. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of nn over all test cases doesn’t exceed 31053⋅105.

Output Distance Tree (hard version) solution codeforces

For each test case, print nn integers in a single line, xx-th of which is equal to f(x)f(x) for all xx from 11 to nn.

Example

input

Copy
3
4
1 2
2 3
1 4
2
1 2
7
1 2
1 3
3 4
3 5
3 6
5 7

output Distance Tree (hard version) solution codeforces

Copy
1 2 2 2 
1 1 
2 2 3 3 3 3 3 
Note

In the first testcase:

  • For x=1x=1, we can an edge between vertices 11 and 33, then d(1)=0d(1)=0 and d(2)=d(3)=d(4)=1d(2)=d(3)=d(4)=1, so f(1)=1f(1)=1.
  • For x2x≥2, no matter which edge we add, d(1)=0d(1)=0d(2)=d(4)=1d(2)=d(4)=1 and d(3)=2d(3)=2, so f(x)=2f(x)=2.
  • For Solution

    Click Here!

Leave a Comment

Your email address will not be published.