Gardener and Tree (Codeforces 1593E)
Tags: Greedy, trees

A tree is an undirected connected graph in which there are no cycles. This problem is about non-rooted trees. A leaf of a tree is a vertex that is connected to at most one vertex.The gardener Vitaly grew a tree from $$$n$$$ vertices. He decided to trim the tree. To do this, he performs a number of operations. In one operation, he removes all leaves of the tree.  Example of a tree. For example, consider the tree shown in the figure above. The figure below shows the result of applying exactly one operation to the tree.  The result of applying the operation "remove all leaves" to the tree. Note the special cases of the operation:  applying an operation to an empty tree (of $$$0$$$ vertices) does not change it;  applying an operation to a tree of one vertex removes this vertex (this vertex is treated as a leaf);  applying an operation to a tree of two vertices removes both vertices (both vertices are treated as leaves). Vitaly applied $$$k$$$ operations sequentially to the tree. How many vertices remain?

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.Each test case is preceded by an empty line.Each test case consists of several lines. The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 4 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — the number of vertices in the tree and the number of operations, respectively. Then $$$n - 1$$$ lines follow, each of them contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.It is guaranteed that the sum of $$$n$$$ from all test cases does not exceed $$$4 \cdot 10^5$$$.

Output: For each test case output on a separate line a single integer — the number of vertices that remain in the tree after applying $$$k$$$ operations.

Note: The first test case is considered in the statement.The second test case contains a tree of two vertices. $$$200000$$$ operations are applied to it. The first one removes all two vertices, the other operations do not change the tree.In the third test case, a tree of three vertices is given. As a result of the first operation, only $$$1$$$ vertex remains in it (with the index $$$2$$$), the second operation makes the tree empty.

Sample Inputs:
6

14 1
1 2
2 3
2 4
4 5
4 6
2 7
7 8
8 9
8 10
3 11
3 12
1 13
13 14

2 200000
1 2

3 2
1 2
2 3

5 1
5 1
3 2
2 1
5 4

6 2
5 1
2 5
5 6
4 2
3 4

7 1
4 3
5 1
1 3
6 1
1 7
2 1

Sample Outputs:
7
0
0
3
1
2

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

def solve(n, k, adj):
    ver = n
    indeg = [len(adj[z]) for z in range(n + 1)]
    bfs = deque()
    for i in range(1, n + 1):
        if indeg[i] == 1:
            bfs.append(i)
    bfs.append(-1)
    while k:
        if ver < 3:
            return 0
        ver -= len(bfs) - 1
        while bfs[0] != -1:
            node = bfs.popleft()
            for each in adj[node]:
                indeg[each] -= 1
                if indeg[each] == 1:
                    bfs.append(each)
        bfs.popleft()
        bfs.append(-1)
        k -= 1
    return ver
t = int(input())
for _ in range(t):
    emp = input()
    (n, k) = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (u, v) = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    print(solve(n, k, adj))

Solution (Python):
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop, heapify
from math import *
from collections import defaultdict, Counter, deque
from functools import lru_cache
from sys import stdin, stdout
import random
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
RANDOM = random.randrange(2 ** 62)
ninput = lambda : int(input())
sinput = lambda : input().decode().strip()
ainput = lambda : list(map(int, input().split()))
print = lambda *x: stdout.write(' '.join(map(str, x)) + '\n')
ceil = lambda a, b: a // b if (a >= 0) ^ (b > 0) else (abs(a) + abs(b) - 1) // abs(b)
Wrapper = lambda x: x ^ RANDOM

def main():
    for z in range(ninput()):
        input()
        (n, k) = ainput()
        adj = defaultdict(list)
        for _ in range(n - 1):
            (u, v) = ainput()
            adj[u].append(v)
            adj[v].append(u)
        rem = [0] * (n + 1)
        for i in adj:
            rem[i] = len(adj[i]) - 1
        op = [-1] * (n + 1)
        que = deque([i for i in adj if len(adj[i]) == 1])
        vis = [0] * (n + 1)
        lvl = 1
        while que:
            l = len(que)
            for _ in range(l):
                p = que.popleft()
                vis[p] = 1
                op[p] = lvl
                for i in adj[p]:
                    if not vis[i]:
                        rem[i] -= 1
                        if not rem[i]:
                            que.append(i)
            lvl += 1
        ans = 0
        for i in op:
            ans += int(i > k)
        print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque
import sys, threading
import heapq
_input = sys.stdin.readline
hpop = heapq.heappop
hpush = heapq.heappush

def _print(*argv, sep=' '):
    sys.stdout.write(sep.join(map(str, argv)) + '\n')

def outbool(val):
    return 'YES' if val else 'NO'

def inp():
    return int(_input())

def inlt():
    return list(map(int, _input().split()))

def insr():
    s = _input()
    return list(s.strip())

def invr():
    return map(int, _input().split())

def solve():
    input()
    (n, k) = invr()
    graph = defaultdict(list)
    incoming = [0] * (n + 1)
    for _ in range(n - 1):
        (u, v) = invr()
        graph[u].append(v)
        graph[v].append(u)
        incoming[u] += 1
        incoming[v] += 1
    queue = deque()
    for i in range(1, n + 1):
        if incoming[i] == 1:
            queue.append(i)
    left = n
    for _ in range(k):
        size = len(queue)
        if size == 0:
            left = 0
            break
        for _ in range(size):
            u = queue.popleft()
            left -= 1
            for v in graph[u]:
                incoming[v] -= 1
                if incoming[v] == 1:
                    queue.append(v)
    _print(left)

def main():
    t = inp()
    for _ in range(t):
        solve()
if __name__ == '__main__':
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)
    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()