Distance Tree (easy version) (Codeforces 1632E1)
Tags: Others, shortest paths

This version of the problem differs from the next 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 3000$$$).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 $$$3000$$$.

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, io, os
try:
    Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
    Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(lambda x: int(x) - 1, Z().split())
from collections import defaultdict as dd
O = []
for _ in range(int(Z())):
    n = int(Z())
    g = dd(list)
    for i in range(n - 1):
        (u, v) = Y()
        g[u].append(v)
        g[v].append(u)
    q = [0]
    nq = []
    p = [-1] * n
    d = [0] * n
    while q:
        v = q.pop()
        for i in g[v]:
            if i != p[v]:
                p[i] = v
                d[i] = d[v] + 1
                nq.append(i)
        if not q:
            (q, nq) = (nq, [])
    c = [0] * n
    cur = pt = max(d)
    r = [-1] * (n + 1)
    for i in d:
        c[i] += 1
    for i in range(cur, n + 1):
        r[i] = pt
    u = [0] * n
    u[v] = 1
    c[d[v]] -= 1
    while pt >= 0 and (not c[pt]):
        pt -= 1
    cur = pt
    r[cur] = pt
    k = 1
    fq = [v]
    fnq = []
    while cur > 1:
        for _ in range(2):
            while fq:
                v = fq.pop()
                for i in g[v]:
                    if not u[i]:
                        u[i] = 1
                        c[d[i]] -= 1
                        while pt >= 0 and (not c[pt]):
                            pt -= 1
                        fnq.append(i)
            (fq, fnq) = (fnq, [])
        nv = pt - k
        for i in range(max(nv, 1), cur):
            r[i] = max(i + k, pt)
        cur = nv
        k += 1
    O.append(' '.join(map(str, r[1:])))
print('\n'.join(O))

Solution (Python):
from collections import deque
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s):
    q = deque()
    q.append(s)
    dist = [-1] * (n + 1)
    dist[s] = 0
    while q:
        i = q.popleft()
        di = dist[i]
        for j in G[i]:
            if dist[j] == -1:
                dist[j] = di + 1
                q.append(j)
    return dist
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    G = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (u, v) = map(int, input().split())
        G[u].append(v)
        G[v].append(u)
    dist1 = bfs(1)
    m = max(dist1)
    d = [[] for _ in range(m + 1)]
    for i in range(1, n + 1):
        d[dist1[i]].append(i)
    ans0 = [m] * (n + 1)
    u = d[m][0]
    dist2 = bfs(u)
    s = set()
    md = 0
    for i in range(m, 0, -1):
        for j in d[i]:
            md = max(md, dist2[j])
        x = md // 2 + md % 2
        ans0[max(i - 1 - x, 0)] = i - 1
    for i in range(n - 1, 0, -1):
        ans0[i] = min(ans0[i], ans0[i + 1])
    ans.append(' '.join(map(str, ans0[1:])))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys

def solve(n, g):
    d = [None] * n
    (q, d[0]) = ([0], 0)
    for i in range(n):
        par = q[i]
        for chd in g[par]:
            if d[chd] is None:
                d[chd] = d[par] + 1
                q.append(chd)
    s = q.pop()
    D = [None] * n
    (Q, D[s]) = ([s], 0)
    for i in range(n):
        par = Q[i]
        for chd in g[par]:
            if D[chd] is None:
                D[chd] = D[par] + 1
                Q.append(chd)
    ans = [d[s]] * n
    if D[Q[-1]] == d[s] * 2:
        return ans
    visit = [False] * n
    i = n - 1
    for node in q:
        visit[node] = True
        while i >= 0 and visit[Q[i]]:
            i -= 1
        m = D[Q[i]]
        z = d[node]
        for x in range(z - (m + 1) // 2):
            ans[x] = min(ans[x], z)
    return ans

def main():
    input = sys.stdin.readline
    tests = int(input()[:-1])
    for _ in range(tests):
        n = int(input()[:-1])
        g = [[] for _ in range(n)]
        for _ in range(n - 1):
            (u, v) = [int(s) for s in input()[:-1].split()]
            g[u - 1].append(v - 1)
            g[v - 1].append(u - 1)
        print(*solve(n, g))
if __name__ == '__main__':
    main()