A Wide, Wide Graph (Codeforces 1805D)
Tags: Greedy, trees

You are given a tree (a connected graph without cycles) with $$$n$$$ vertices. Consider a fixed integer $$$k$$$. Then, the graph $$$G_k$$$ is an undirected graph with $$$n$$$ vertices, where an edge between vertices $$$u$$$ and $$$v$$$ exists if and only if the distance between vertices $$$u$$$ and $$$v$$$ in the given tree is at least $$$k$$$.For each $$$k$$$ from $$$1$$$ to $$$n$$$, print the number of connected components in the graph $$$G_k$$$.

Input: The first line contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the graph.Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$ in the tree. It is guaranteed that these edges form a valid tree.

Output: Output $$$n$$$ integers: the number of connected components in the graph $$$G_k$$$ for each $$$k$$$ from $$$1$$$ to $$$n$$$.

Note: In the first example: If $$$k=1$$$, the graph has an edge between each pair of vertices, so it has one component. If $$$k=4$$$, the graph has only edges $$$4 \leftrightarrow 6$$$ and $$$5 \leftrightarrow 6$$$, so the graph has $$$4$$$ components.In the second example: when $$$k=1$$$ or $$$k=2$$$ the graph has one component. When $$$k=3$$$ the graph $$$G_k$$$ splits into $$$3$$$ components: one component has vertices $$$1$$$, $$$4$$$ and $$$5$$$, and two more components contain one vertex each. When $$$k=4$$$ or $$$k=5$$$ each vertex is a separate component.

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

5
1 2
2 3
3 4
3 5

Sample Outputs:
1 1 2 4 6 6

1 1 3 5 5

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)

def dfs(node: int, d):
    stack = [node]
    d[node] = 0
    vis = [False] * n
    while stack:
        c = stack.pop()
        vis[c] = True
        for v in g[c]:
            if not vis[v]:
                d[v] = d[c] + 1
                stack.append(v)
(d1, d2) = ([0] * n for _ in range(2))
dfs(0, d1)
dfs(d1.index(max(d1)), d1)
dfs(d1.index(max(d1)), d2)
for i in range(n):
    d2[i] = max(d2[i], d1[i])
d2.sort()
ans = 0
for k in range(1, n + 1):
    while ans < n and d2[ans] < k:
        ans += 1
    print(min(n, ans + 1), end=' ')

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

def INF(x):
    if not x:
        while 1:
            print()

def solve():
    n = int(input())
    g = [[] for i in range(n)]
    for i in range(n - 1):
        (a, b) = map(int, input().split())
        a -= 1
        b -= 1
        INF(a >= 0 and a < n)
        INF(b >= 0 and b < n)
        g[a].append(b)
        g[b].append(a)

    def dfs(G, distance, node0, par, deep):
        st = [(node0, par, deep)]
        for i in range(n):
            (u, f, d) = st[i]
            distance[u] = d
            for v in g[u]:
                if v != f:
                    st.append((v, u, d + 1))
    dis_0 = [0] * n
    dfs(g, dis_0, 0, -1, 0)
    mx = max(dis_0)
    for i in range(n):
        if dis_0[i] == mx:
            p1 = i
            break
    dis_p1 = [0] * n
    dfs(g, dis_p1, p1, -1, 0)
    mx = max(dis_p1)
    for i in range(n):
        if dis_p1[i] == mx:
            p2 = i
            break
    dis_p2 = [0] * n
    dfs(g, dis_p2, p2, -1, 0)
    dis = [0] * n
    for i in range(n):
        dis[i] = max(dis_p1[i], dis_p2[i])
    cnt = [0] * n
    for i in range(n):
        cnt[dis[i]] += 1
    ans = [0] * (n + 1)
    for i in range(n - 1, 0, -1):
        ans[i] = ans[i + 1] + cnt[i]

    def ff(n, i):
        if i == n:
            return 1
        if i == 0:
            return n
        return n - i + 1
    print(' '.join([str(ff(n, i)) for i in ans[1:n + 1]]))

def main():
    if len(sys.argv) >= 2 and sys.argv[1] == 'LOCAL':
        sys.stdin = open('in.txt', 'r')
    tt = 1
    while tt:
        solve()
        tt -= 1
main()

Solution (Python):
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)

def dfs(node: int, d):
    stack = [node]
    d[node] = 0
    visited = [False] * n
    while stack:
        c = stack.pop()
        visited[c] = True
        for v in g[c]:
            if not visited[v]:
                d[v] = d[c] + 1
                stack.append(v)
(d1, d2) = [[0] * n for _ in range(2)]
dfs(0, d1)
dfs(d1.index(max(d1)), d1)
dfs(d1.index(max(d1)), d2)
for i in range(n):
    d2[i] = max(d1[i], d2[i])
d2.sort()
ans = 0
for k in range(1, n + 1):
    while ans < n and d2[ans] < k:
        ans += 1
    print(min(n, ans + 1), end=' ')