Removing Leaves (Codeforces 1385F)
Tags: Greedy, trees

You are given a tree (connected graph without cycles) consisting of $$$n$$$ vertices. The tree is unrooted — it is just a connected undirected graph without cycles.In one move, you can choose exactly $$$k$$$ leaves (leaf is such a vertex that is connected to only one another vertex) connected to the same vertex and remove them with edges incident to them. I.e. you choose such leaves $$$u_1, u_2, \dots, u_k$$$ that there are edges $$$(u_1, v)$$$, $$$(u_2, v)$$$, $$$\dots$$$, $$$(u_k, v)$$$ and remove these leaves and these edges.Your task is to find the maximum number of moves you can perform if you remove leaves optimally.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k < n$$$) — the number of vertices in the tree and the number of leaves you remove in one move, respectively. The next $$$n-1$$$ lines describe edges. The $$$i$$$-th edge is represented as two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$), where $$$x_i$$$ and $$$y_i$$$ are vertices the $$$i$$$-th edge connects. It is guaranteed that the given set of edges forms a tree.It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output: For each test case, print the answer — the maximum number of moves you can perform if you remove leaves optimally.

Note: The picture corresponding to the first test case of the example:There you can remove vertices $$$2$$$, $$$5$$$ and $$$3$$$ during the first move and vertices $$$1$$$, $$$7$$$ and $$$4$$$ during the second move.The picture corresponding to the second test case of the example:There you can remove vertices $$$7$$$, $$$8$$$ and $$$9$$$ during the first move, then vertices $$$5$$$, $$$6$$$ and $$$10$$$ during the second move and vertices $$$1$$$, $$$3$$$ and $$$4$$$ during the third move.The picture corresponding to the third test case of the example:There you can remove vertices $$$5$$$ and $$$7$$$ during the first move, then vertices $$$2$$$ and $$$4$$$ during the second move and vertices $$$1$$$ and $$$6$$$ during the third move.

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

Sample Outputs:
2
3
3
4

Solution (Python):
t = int(input())
Maxn = 210000
while t > 0:
    t -= 1
    (n, k) = map(int, input().split())
    d = [0] * (n + 1)
    bj = [0] * (n + 1)
    flag = [0] * (n + 1)
    to = [[]]
    for i in range(0, n):
        to.append([])
    for i in range(1, n):
        (u, v) = map(int, input().split())
        to[u].append(v)
        to[v].append(u)
        d[u] += 1
        d[v] += 1
    if k == 1:
        print(n - 1)
        continue
    que = []
    for i in range(1, n + 1):
        if d[i] == 1:
            bj[to[i][0]] += 1
            flag[i] = 1
    for i in range(1, n + 1):
        if bj[i] >= k:
            que.append(i)
    ans = 0
    while len(que):
        now = que.pop()
        ans += 1
        bj[now] -= k
        if bj[now] >= k:
            que.append(now)
            continue
        if bj[now]:
            continue
        sxz = 0
        nh = 0
        for i in to[now]:
            if flag[i] == 0:
                sxz += 1
                nh = i
        if sxz == 1:
            flag[now] = 1
            bj[nh] += 1
            if bj[nh] == k:
                que.append(nh)
    print(ans)

Solution (Python):
from collections import defaultdict
import sys, math
f = None
try:
    f = open('q1.input', 'r')
except IOError:
    f = sys.stdin
if 'xrange' in dir(__builtins__):
    range = xrange
sys.setrecursionlimit(10 ** 6)

def print_case_iterable(case_num, iterable):
    print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
    print('Case #{}: {}'.format(case_num, iterable))

def print_iterable(A):
    print(' '.join(A))

def read_int():
    return int(f.readline().strip())

def read_int_array():
    return [int(x) for x in f.readline().strip().split(' ')]

def rns():
    a = [x for x in f.readline().split(' ')]
    return (int(a[0]), a[1].strip())

def read_string():
    return list(f.readline().strip())

def ri():
    return int(f.readline().strip())

def ria():
    return [int(x) for x in f.readline().strip().split(' ')]

def rns():
    a = [x for x in f.readline().split(' ')]
    return (int(a[0]), a[1].strip())

def rs():
    return list(f.readline().strip())

def bi(x):
    return bin(x)[2:]
from collections import deque
import math
NUMBER = 10 ** 9 + 7

def factorial(n):
    M = NUMBER
    f = 1
    for i in range(1, n + 1):
        f = f * i % M
    return f

def mult(a, b):
    return a * b % NUMBER

def minus(a, b):
    return (a - b) % NUMBER

def plus(a, b):
    return (a + b) % NUMBER

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        (g, y, x) = egcd(b % a, a)
        return (g, x - b // a * y, y)

def modinv(a):
    m = NUMBER
    (g, x, y) = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def choose(n, k):
    if n < k:
        assert false
    return mult(factorial(n), modinv(mult(factorial(k), factorial(n - k)))) % NUMBER
from collections import deque, defaultdict
import heapq
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def dfs(g, timeIn, timeOut, depths, parents):
    cnt = 0
    stack = [[1, 0, 0, 0]]
    while stack:
        (v, neig_i, parent, depth) = stack[-1]
        parents[v] = parent
        depths[v] = depth
        if neig_i == 0:
            timeIn[v] = cnt
            cnt += 1
        while neig_i < len(g[v]):
            u = g[v][neig_i]
            if u == parent:
                neig_i += 1
                continue
            stack[-1][1] = neig_i + 1
            stack.append([u, 0, v, depth + 1])
            break
        if neig_i == len(g[v]):
            stack.pop()
            timeOut[v] = cnt
            cnt += 1
cnt = 0

@bootstrap
def dfs(v, adj, timeIn, timeOut, depths, parents, parent=0, depth=0):
    global cnt
    parents[v] = parent
    depths[v] = depth
    timeIn[v] = cnt
    cnt += 1
    for u in adj[v]:
        if u == parent:
            continue
        yield dfs(u, adj, timeIn, timeOut, depths, parents, v, depth + 1)
    timeOut[v] = cnt
    cnt += 1
    yield

def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)

def lcm(a, b):
    return a * b / gcd(a, b)

def get_num_2_5(n):
    twos = 0
    fives = 0
    while n > 0 and n % 2 == 0:
        n //= 2
        twos += 1
    while n > 0 and n % 5 == 0:
        n //= 5
        fives += 1
    return (twos, fives)

def shift(a, i, num):
    for _ in range(num):
        (a[i], a[i + 1], a[i + 2]) = (a[i + 2], a[i], a[i + 1])

def equal(x, y):
    return abs(x - y) <= 1e-09

def getAngle(a, b, c):
    ang = math.degrees(math.atan2(c[1] - b[1], c[0] - b[0]) - math.atan2(a[1] - b[1], a[0] - b[0]))
    return ang + 360 if ang < 0 else ang

def getLength(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
from heapq import heapify, heappush, heappop

def bfs(adj):
    s = set()
    d = defaultdict(set)
    q = deque([])
    s.add(0)
    d[0].add(0)
    q.append((0, 0))
    while len(q) > 0:
        (v, depth) = q.popleft()
        for u in adj[v]:
            if u not in s:
                s.add(u)
                d[depth + 1].add(u)
                q.append((u, depth + 1))
    return d

def solution(adj, n, k):
    if k == 1:
        return n - 1
    if n == 2:
        return 0
    leaves = [set() for i in range(n)]
    stack = []
    for v in range(n):
        if len(adj[v]) == 1:
            leaves[adj[v].pop()].add(v)
    for v in range(n):
        if len(leaves[v]) >= k:
            stack.append(v)
    cnt = 0
    while len(stack) > 0:
        cnt += 1
        v = stack.pop()
        ls = set()
        try:
            for i in range(k):
                ls.add(leaves[v].pop())
        except:
            return f'{cnt}000{n}000{k}'
        adj[v] -= ls
        if len(adj[v]) == 0:
            continue
        elif len(adj[v]) == 1:
            u = adj[v].pop()
            leaves[u].add(v)
            if len(leaves[u]) == k:
                stack.append(u)
        elif len(leaves[v]) >= k:
            stack.append(v)
    return cnt

def main():
    T = 1
    T = ri()
    for i in range(T):
        (n, k) = ria()
        adj = [set() for _ in range(n)]
        for _ in range(n - 1):
            (a, b) = ria()
            a -= 1
            b -= 1
            adj[a].add(b)
            adj[b].add(a)
        x = solution(adj, n, k)
        if 'xrange' not in dir(__builtins__):
            print(x)
        else:
            (print >> output, str(x))
    if 'xrange' in dir(__builtins__):
        print(output.getvalue())
        output.close()
if 'xrange' in dir(__builtins__):
    import cStringIO
    output = cStringIO.StringIO()
if __name__ == '__main__':
    main()

Solution (Python):
import collections
t = int(input())
for i in range(t):
    (n, k) = map(int, input().split())
    g = collections.defaultdict(list)
    for j in range(n - 1):
        (x, y) = map(int, input().split())
        g[x].append(y)
        g[y].append(x)
    if k == 1:
        print(n - 1)
    else:
        leaf = {}
        a = set()
        b = {}
        l = {}
        for v in g:
            p = 0
            q = 0
            for u in g[v]:
                q = q + 1
                if len(g[u]) == 1:
                    p = p + 1
                    leaf[u] = 1
            if p >= k:
                a.add(v)
            b[v] = p
            l[v] = q
        c = 0
        while a != set():
            p = a.pop()
            te = b[p] // k
            c = c + te
            if b[p] % k == 0 and l[p] - te * k == 1:
                leaf[p] = 1
                b[p] = 0
                l[p] = 1
                for v in g[p]:
                    if v not in leaf:
                        b[v] = b[v] + 1
                        if b[v] >= k:
                            a.add(v)
                        break
            else:
                b[p] = b[p] - te * k
                l[p] = l[p] - te * k
        print(c)