Tree Cutting (Codeforces 1946C)
Tags: Greedy, trees

You are given a tree with $$$n$$$ vertices.Your task is to find the maximum number $$$x$$$ such that it is possible to remove exactly $$$k$$$ edges from this tree in such a way that the size of each remaining connected component$$$^{\dagger}$$$ is at least $$$x$$$.$$$^{\dagger}$$$ Two vertices $$$v$$$ and $$$u$$$ are in the same connected component if there exists a sequence of numbers $$$t_1, t_2, \ldots, t_k$$$ of arbitrary length $$$k$$$, such that $$$t_1 = v$$$, $$$t_k = u$$$, and for each $$$i$$$ from $$$1$$$ to $$$k - 1$$$, vertices $$$t_i$$$ and $$$t_{i+1}$$$ are connected by an edge.

Input: Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of sets of input data. This is followed by a description of the sets of input data.The first line of each set of input data contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 10^5$$$) — the number of vertices in the tree and the number of edges to be removed.Each of the next $$$n - 1$$$ lines of each set of input data contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$) — the next edge of the tree.It is guaranteed that the sum of the values of $$$n$$$ for all sets of input data does not exceed $$$10^5$$$.

Output: For each set of input data, output a single line containing the maximum number $$$x$$$ such that it is possible to remove exactly $$$k$$$ edges from the tree in such a way that the size of each remaining connected component is at least $$$x$$$.

Note: The tree in the first set of input data:  After removing the edge $$$1$$$ — $$$3$$$, the tree will look as follows:  The tree has split into two connected components. The first component consists of two vertices: $$$1$$$ and $$$2$$$. The second connected component consists of three vertices: $$$3, 4$$$ and $$$5$$$. In both connected components, there are at least two vertices. It can be shown that the answer $$$3$$$ is not achievable, so the answer is $$$2$$$.

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

Sample Outputs:
2
1
3
1
1
2

Solution (Python):
t_num = int(input())
r = []
mod = 10 ** 9 + 7

def solve():
    (n, k) = list(map(int, input().split()))
    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        (a, b) = list(map(int, input().split()))
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    visited = [0] * n
    visited[0] = 1
    prev = [-1]
    cur = [0]
    t = 0
    while cur:
        ncur = []
        for i in cur:
            for v in edge[i]:
                if visited[v]:
                    continue
                visited[v] = 1
                ncur.append(v)
                prev.append(t)
            t += 1
        cur = ncur
    lo = 1
    hi = n
    while lo <= hi:
        mid = (lo + hi) // 2
        val = [1] * n
        count = -1
        for i in range(n - 1, -1, -1):
            if val[i] >= mid:
                count += 1
            else:
                val[prev[i]] += val[i]
        if count >= k:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi
for _ in range(t_num):
    r.append(solve())
for i in r:
    print(i)

Solution (Python):
t_num = int(input())
r = []
mod = 10 ** 9 + 7

def solve():
    (n, k) = list(map(int, input().split()))
    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        (a, b) = list(map(int, input().split()))
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    visited = [0] * n
    visited[0] = 1
    prev = [-1]
    cur = [0]
    t = 0
    while cur:
        ncur = []
        for i in cur:
            for v in edge[i]:
                if visited[v]:
                    continue
                visited[v] = 1
                ncur.append(v)
                prev.append(t)
            t += 1
        cur = ncur
    lo = 1
    hi = n
    while lo <= hi:
        mid = (lo + hi) // 2
        val = [1] * n
        count = -1
        for i in range(n - 1, -1, -1):
            if val[i] >= mid:
                count += 1
            else:
                val[prev[i]] += val[i]
        if count >= k:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi
for _ in range(t_num):
    r.append(solve())
for i in r:
    print(i)

Solution (Python):
line = lambda : list(map(int, input().split()))
for _ in range(int(input())):
    (n, k) = line()
    g = [[] for _ in range(n + 1)]
    deg = [0 for _ in range(n + 1)]
    for _ in range(n - 1):
        (u, v) = line()
        g[u].append(v)
        g[v].append(u)
        deg[u] += 1
        deg[v] += 1
    ''
    dfs = [1]
    ant = [0] * (n + 1)
    i = 0
    while i < len(dfs):
        u = dfs[i]
        for v in g[u]:
            if v != ant[u]:
                ant[v] = u
                dfs.append(v)
        i += 1
    (l, r) = (1, n + 1)
    while r - l > 1:
        m = (l + r) // 2
        size = [1] * (n + 1)
        kk = k
        ok = False
        i = n - 1
        while i >= 0:
            u = dfs[i]
            if size[u] < m:
                size[ant[u]] += size[u]
            else:
                kk -= 1
                if kk < 0:
                    ok = True
                    break
            i -= 1
        if ok or i >= m:
            l = m
        else:
            r = m
    print(l)