Distance Tree (hard version) (Codeforces 1632E2)
Tags: Others, shortest paths

This version of the problem differs from the previous one only in the constraint on $$$n$$$.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 $$$n$$$ vertices, each edge has a weight of $$$1$$$. Denote $$$d(v)$$$ as the distance between vertex $$$1$$$ and vertex $$$v$$$.Let $$$f(x)$$$ be the minimum possible value of $$$\max\limits_{1 \leq v \leq n} \ {d(v)}$$$ if you can temporarily add an edge with weight $$$x$$$ between any two vertices $$$a$$$ and $$$b$$$ $$$(1 \le a, b \le n)$$$. Note that after this operation, the graph is no longer a tree.For each integer $$$x$$$ from $$$1$$$ to $$$n$$$, find $$$f(x)$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).Each of the next $$$n−1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) indicating that there is an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print $$$n$$$ integers in a single line, $$$x$$$-th of which is equal to $$$f(x)$$$ for all $$$x$$$ from $$$1$$$ to $$$n$$$.

Note:    In the first testcase:   For $$$x = 1$$$, we can an edge between vertices $$$1$$$ and $$$3$$$, then $$$d(1) = 0$$$ and $$$d(2) = d(3) = d(4) = 1$$$, so $$$f(1) = 1$$$.  For $$$x \ge 2$$$, no matter which edge we add, $$$d(1) = 0$$$, $$$d(2) = d(4) = 1$$$ and $$$d(3) = 2$$$, so $$$f(x) = 2$$$. 

Sample Inputs:
3
4
1 2
2 3
1 4
2
1 2
7
1 2
1 3
3 4
3 5
3 6
5 7

Sample Outputs:
1 2 2 2 
1 1 
2 2 3 3 3 3 3

Solution (Python):
import sys
import math

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    g = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (u, v) = map(int, inp().split())
        g[u].append(v)
        g[v].append(u)
    q = [1]
    d = [None] * (n + 1)
    d[1] = 0
    for qi in range(n):
        x = q[qi]
        for v in g[x]:
            if d[v] is None:
                d[v] = d[x] + 1
                q.append(v)
    w = [False] * (n + 1)
    s = q[-1]
    Q = [s]
    D = [None] * (n + 1)
    D[s] = 0
    for qi in range(n):
        u = Q[qi]
        for v in g[u]:
            if D[v] is None:
                D[v] = D[u] + 1
                Q.append(v)
    q.pop()
    j = n - 1
    p = 0
    ans = [d[s]] * n
    z = n
    for x in q:
        w[x] = True
        while w[Q[j]]:
            j -= 1
        m = D[Q[j]]
        z = d[x]
        v = z - (m + 1) // 2 - 1
        for k in range(p, v + 1):
            ans[k] = min(ans[k], z)
        p = max(0, v)
    for j in range(p, v + 1):
        ans[j] = min(ans[j], z)
    print(' '.join(map(str, ans)))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    g = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (u, v) = map(int, inp().split())
        g[u].append(v)
        g[v].append(u)
    q = [1]
    d = [None] * (n + 1)
    d[1] = 0
    for qi in range(n):
        x = q[qi]
        for v in g[x]:
            if d[v] is None:
                d[v] = d[x] + 1
                q.append(v)
    w = [False] * (n + 1)
    s = q[-1]
    Q = [s]
    D = [None] * (n + 1)
    D[s] = 0
    for qi in range(n):
        u = Q[qi]
        for v in g[u]:
            if D[v] is None:
                D[v] = D[u] + 1
                Q.append(v)
    q.pop()
    j = n - 1
    p = 0
    ans = [d[s]] * n
    z = n
    for x in q:
        w[x] = True
        while w[Q[j]]:
            j -= 1
        m = D[Q[j]]
        z = d[x]
        v = z - (m + 1) // 2 - 1
        for k in range(p, v + 1):
            ans[k] = min(ans[k], z)
        p = max(0, v)
    for j in range(p, v + 1):
        ans[j] = min(ans[j], z)
    print(' '.join(map(str, ans)))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    g = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (u, v) = map(int, inp().split())
        g[u].append(v)
        g[v].append(u)
    q = [1]
    d = [None] * (n + 1)
    d[1] = 0
    for qi in range(n):
        x = q[qi]
        for v in g[x]:
            if d[v] is None:
                d[v] = d[x] + 1
                q.append(v)
    w = [False] * (n + 1)
    s = q[-1]
    Q = [s]
    D = [None] * (n + 1)
    D[s] = 0
    for qi in range(n):
        u = Q[qi]
        for v in g[u]:
            if D[v] is None:
                D[v] = D[u] + 1
                Q.append(v)
    q.pop()
    j = n - 1
    p = []
    for x in q:
        w[x] = True
        while w[Q[j]]:
            j -= 1
        m = D[Q[j]]
        z = d[x]
        v = z - (m + 1) // 2 - 1
        p.append((v, z))
    ans = [d[s]] * n
    for i in range(1, len(p)):
        (v, z) = p[i - 1]
        (v1, z1) = p[i]
        for j in range(max(v, 0), v1 + 1):
            ans[j] = min(ans[j], z1)
    if len(p):
        (v, z) = p[0]
        for j in range(0, v + 1):
            ans[j] = min(ans[j], z)
        (v, z) = p[-1]
    print(' '.join(map(str, ans)))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()