Problem:
 Score : 600 points    Problem Statement Given an undirected tree, let the distance between vertices u and v be the
number of edges on the simple path from u to v .
The diameter of a tree is the maximum among the distances between any two vertices.
We will call a tree good if and only if its diameter is at most K .  You are given an undirected tree with N vertices numbered 1 through N .
For each i (1≦i≦N-1) , there is an edge connecting vertices A_i and B_i .  You want to remove zero or more vertices from the tree, so that the resulting tree is good.
When a vertex is removed, all incident edges will also be removed.
The resulting graph must be connected.  Find the minimum number of vertices that you need to remove in order to produce a good tree.      Constraints  2≦N≦2000  1≦K≦N-1  1≦A_i≦N, 1≦B_i≦N  The graph defined by A_i and B_i is a tree.         Input The input is given from Standard Input in the following format:  N  K  A_1  B_1  A_2  B_2 : A_{N-1}  B_{N-1}       Output Print the minimum number of vertices that you need to remove in order to produce a good tree.        Sample Input 1 6 2
1 2
3 2
4 2
1 6
5 6      Sample Output 1 2  The tree is shown below. Removing vertices 5 and 6 will result in a good tree with the diameter of 2 .          Sample Input 2 6 5
1 2
3 2
4 2
1 6
5 6      Sample Output 2 0  Since the given tree is already good, you do not need to remove any vertex.

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,k = map(int, input().split())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    dist = defaultdict(list)
    dist[0].append(start)
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None and v not in done:
                seen[v] = d + 1
                dist[d+1].append(v)
                q.appendleft(v)
    return seen, dist
ans = 0
done = set()
while True:
    start = 0
    while start in done:
        start += 1
    seen, dist1 = bfs(start)
    m = max(item for item in seen if item is not None)
    u = dist1[m][0]
    seen, dist1 = bfs(u)
    mm = max(item for item in seen if item is not None)
    if mm<=k:
        break
    ans += 1
    v = dist1[mm][0]
    seen, dist2 = bfs(v)
    v1 = sum(len(dist1[u]) for u in range(k+1, mm+1))
    v2 = sum(len(dist2[u]) for u in range(k+1, mm+1))
    if v1<v2:
        done.add(v)
    else:
        done.add(u)
print(ans)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
m = map(int, read().split())
G = [[] for _ in range(N + 1)]
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)

def dfs_order(G, root=1):
    parent = [0] * (N + 1)
    order = []
    stack = [root]
    while stack:
        x = stack.pop()
        order.append(x)
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)
    return parent, order

parent, order = dfs_order(G)

dp1 = np.zeros((N + 1, N + 1), np.int32)
for v in order[::-1]:
    p = parent[v]
    dp1[v, 0] += 1
    dp1[p, 1:] += dp1[v, :-1]

dp2 = np.zeros((N + 1, N + 1), np.int32)
dp2[1] = dp1[1]
for v in order[1:]:
    p = parent[v]
    x = dp2[p].copy()
    x[1:] -= dp1[v, :-1]
    dp2[v, 1:] += x[:-1]
    dp2[v] += dp1[v]

dp3 = np.zeros((N + 1, N + 1), np.int32)
for v in order[1:]:
    p = parent[v]
    dp3[v] = dp1[v]
    x = dp2[p].copy()
    x[1:] -= dp1[v][:-1]
    dp3[v] += x


dp2.cumsum(axis=1, out=dp2)
dp3.cumsum(axis=1, out=dp3)

if K % 2 == 0:
    x = dp2[:, K // 2].max()
else:
    x = dp3[:, K // 2].max()

print(N - x)

Solution (Python):
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
ans = n
rad = k//2
for center in range(1,n+1):
  stack = [center]
  dep = [[-1,-1] for _ in range(n+1)]
  dep[center] = [0,0]
  while stack:
    x = stack.pop()
    for i,y in enumerate(graph[x]):
      if x == center:
        dep[y] = [1,i+1]
        stack.append(y)
      else:
        if dep[y][0] == -1:
          stack.append(y)
          dep[y][0] = dep[x][0]+1
          dep[y][1] = dep[x][1]
  anstmp = 0
  bonus = [0]*(len(graph[center])+1)
  for i in range(1,n+1):
    if dep[i][0] <= rad:
      anstmp += 1
    if dep[i][0] == rad+1:
      bonus[dep[i][1]] += 1
  if k%2:
    anstmp += max(bonus)
  ans = min(n-anstmp,ans)
print(max(ans,0))

Solution (Python):


from collections import defaultdict,deque

N,K=map(int,input().split())
tree=[]
Graph=defaultdict(list)

for _ in range(N-1):
  edge=list(map(int,input().split()))
  Graph[edge[0]].append(edge[1])
  Graph[edge[1]].append(edge[0])
  tree.append(edge)
  
def DFSans(start,diam):
  visited=[0]*N
  q=deque()
  for s in start:
    q.append((s,0))
    visited[s-1]=1
  while q:
    search,start_diam=q.pop()
    if start_diam>=diam:
      continue
    for n in Graph[search]:
      if visited[n-1]:
        continue
      q.append((n,start_diam+1))
      visited[n-1]=1
    
  return N-sum(visited)

ans=99999999999999999999
if K%2==1:
  for i in range(N-1):
    ans=min(ans,DFSans(tree[i],(K-1)//2))
else:
  for i in range(1,N+1):
    ans=min(ans,DFSans([i],K//2))
print(ans)

Solution (Python):
import sys
from collections import deque


def bfs(links, s, limit, bits):
    not_reachable = (1 << len(links)) - 1
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable ^= bits[v]
        cost += 1
        for u in links[v]:
            if u != p:
                q.append((cost, u, v))
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in ab:
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    limit = k // 2
    bits = [1 << i for i in range(n)]
    if k % 2 == 0:
        ans = min(bin(bfs(links, v, limit, bits)).count('1') for v in range(n))
    else:
        dists = [bfs(links, v, limit, bits) for v in range(n)]
        ans = min(bin(dists[a - 1] & dists[b - 1]).count('1') for a, b in ab)
    return ans


n, k = map(int, sys.stdin.buffer.readline().split())
ab = map(int, sys.stdin.buffer.read().split())
ab = list(zip(ab, ab))
print(solve(n, k, ab))

Solution (Python):
import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = [True] * len(links)
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable[v] = False
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in zip(ab[0::2], ab[1::2]):
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    ans = n
    thr = k // 2
    if k % 2 == 0:
        ans = min(sum(bfs(links, v, thr)) for v in range(n))
    else:
        dists = [bfs(links, v, thr) for v in range(n)]
        for a, b in zip(ab[0::2], ab[1::2]):
            a -= 1
            b -= 1
            ans = min(ans, sum(d1 and d2 for d1, d2 in zip(dists[a], dists[b])))
    return ans


n, k, *ab = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, ab))

Solution (Python):
n,k = map(int, input().split())
link = [[] for _ in range(n)]
ln = []
for i in range(n-1):
    a,b = list(map(int,input().split()))
    link[a-1].append(b-1)
    link[b-1].append(a-1)
    ln.append([a-1,b-1])

if k==1:
    print(n-2)
    exit()

from collections import deque
def get_v(node,dist):
    Q = deque()
    Q.append([node,0])
    visited=[-1]*n
    visited[node]=1
    while Q:
        now,cnt = Q.popleft()
        if cnt > dist:
            break
        for nxt in link[now]:
            if visited[nxt]!=-1:
                continue
            visited[nxt]=cnt+1
            Q.append([nxt,cnt+1])
    for i in range(n):
        if visited[i] == -1:
            ret = 0
        elif visited[i] <= dist:
            ret = 1
        else:
            ret = 0
        visited[i] = ret
    return visited
def borsm(l1,l2):
    sm=0
    for b1,b2 in zip(l1,l2):
        sm+=(b1 | b2)
    return sm
ans=float("inf")
if k%2==0:
    for i in range(n):
        ret = n - sum(get_v(i,k//2))
        ans=min(ret,ans)
else:
    for tmp in ln:
        n1,n2=tmp
        c1=get_v(n1,k//2)
        c2=get_v(n2,k//2)
        ret = n- borsm(c1,c2)
        ans=min(ret,ans)
print(ans)

Solution (Python):
n, k = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
if k % 2 == 0:
    ans = 100000
    for i in range(n):
        s = [i]
        d = [-1] * n
        d[i] = 0
        while s:
            p = s.pop()
            for node in g[p]:
                if d[node] == -1:
                    s.append(node)
                    d[node] = d[p] + 1
        c = 0
        for i in range(n):
            if d[i] > k // 2:
                c += 1
        ans = min(ans, c)
else:
    ans = 100000
    for i in range(n):
        for j in g[i]:
            s = [i, j]
            d = [-1] * n
            d[i] = 0
            d[j] = 0
            while s:
                p = s.pop()
                for node in g[p]:
                    if d[node] == -1:
                        s.append(node)
                        d[node] = d[p] + 1
            c = 0
            for p in range(n):
                if d[p] > k // 2:
                    c += 1
            ans = min(ans, c)
print(ans)

Solution (Python):



from collections import deque

def main():

    n, d = map(int, input().split())

    adj = [[] for i in range(n)]

    edges = []

    for i in range(n-1):

        a, b = map(int, input().split())

        adj[a-1].append(b-1)

        adj[b-1].append(a-1)

        edges.append((a-1, b-1))


    ans = 1000000

    if (d % 2 == 0):
        for i in range(n):
            ans = min(ans, compute(adj, i, d))
    else:
        for i in range(n-1):
            ans = min(ans, computeEdges(adj, edges[i], d-1))

    print(ans)

def compute(adj, u, dia):

    vis = [False]*len(adj)

    dis = [0]*len(adj)

    q = deque()

    q.append(u)
    vis[u] = True

    while (len(q) > 0):

        elem = q.popleft()

        for v in adj[elem]:

            if (vis[v] == False):
                q.append(v)

                vis[v] = True

                dis[v] = dis[elem] + 1

    count = 0

    for a in dis:

        if (a > dia/2):
            count += 1

    return count


def computeEdges(adj, edge, dia):

    vis = [False]*len(adj)

    dis = [0]*len(adj)

    q = deque()

    q.append(edge[0])
    q.append(edge[1])
    vis[edge[0]] = True
    vis[edge[1]] = True

    while (len(q) > 0):

        elem = q.popleft()

        for v in adj[elem]:

            if (vis[v] == False):
                q.append(v)

                vis[v] = True

                dis[v] = dis[elem] + 1

    count = 0

    for a in dis:

        if (a > dia/2):
            count += 1

    return count

main()

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc001/tasks/agc001_c

今度こそ通すぞ！！
制約が小さいので、各頂点に関して最短距離探索するぐらいはできる

直径の中央で全探索する？
→距離K//2以内の頂点の数を数え、残りを取り除けばよい
→その点を通らない長さK以上のパスは存在しえない

Kが偶数なら、1点を中心(深さ0)とし探索
Kが奇数なら、隣接する2点を深さ0とすればよい

計算量はO(N**2)

"""
from collections import deque
N,K = map(int,input().split())

AB = []

lis = [ [] for i in range(N) ]

for i in range(N-1):

    A,B = map(int,input().split())

    A -= 1
    B -= 1

    lis[A].append(B)
    lis[B].append(A)

    AB.append([A,B])

ans = float("inf")

if K % 2 == 0: 

    for st in range(N):
        q = deque([st])
        dis = [float("inf")] * N
        dis[st] = 0
        nps = 0

        while len(q) > 0:

            now = q.popleft()
            nps += 1

            if dis[now] < K//2:

                for nex in lis[now]:
                    if dis[nex] > dis[now] + 1:
                        dis[nex] = dis[now] + 1
                        q.append(nex)
                        
        ans = min(ans , N - nps)

else:

    for i in range(N-1):
        a,b = AB[i]
        q = deque([a,b])
        dis = [float("inf")] * N
        dis[a] = 0
        dis[b] = 0
        nps = 0

        while len(q) > 0:

            now = q.popleft()
            nps += 1

            if dis[now] < K//2:

                for nex in lis[now]:
                    if dis[nex] > dis[now] + 1:
                        dis[nex] = dis[now] + 1
                        q.append(nex)
                        
        ans = min(ans , N - nps)   

print (ans)

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

def main():
  n, k = map(int, input().split())
  T = [[] for _ in range(n)]
  E = []
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))
  d = k//2
  def dfs(vs):
    dist = [-1]*n
    stack = []
    cnt = 0
    for v in vs:
      stack.append(v)
      dist[v] = 0
    while stack:
      v = stack.pop()
      for nv in T[v]:
        if dist[nv] == -1:
          dist[nv] = dist[v] + 1
          if dist[nv] > d:
            cnt += 1
          stack.append(nv)
    return cnt
  ans = n
  if k%2 == 0:
    for i in range(n):
      ans = min(ans, dfs([i]))
  else:
    for l in E:
      ans = min(ans, dfs(l))
  print(ans)
  
if __name__ == "__main__":
  main()

Solution (Python):
n, k = map(int, input().split())
T = [[] for _ in range(n)]
E = []
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
  E.append((a, b))
d = k//2
def dfs(vs):
  dist = [-1]*n
  stack = []
  cnt = 0
  for v in vs:
    stack.append(v)
    dist[v] = 0
  while stack:
    v = stack.pop()
    for nv in T[v]:
      if dist[nv] == -1:
        dist[nv] = dist[v] + 1
        if dist[nv] > d:
          cnt += 1
        stack.append(nv)
  return cnt
ans = n
if k%2 == 0:
  for i in range(n):
    ans = min(ans, dfs([i]))
else:
  for l in E:
    ans = min(ans, dfs(l))
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque

n, k = map(int, input().split())
radius = k // 2
edge = [[] for _ in range(n)]
uv = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
    uv.append((a, b))

def dfs(p, v, d):
    ret = 0
    st = []
    st.append((p, v, d))
    while st:
        p, v, d = st.pop()
        if d > radius:
            ret += 1
        for nv in edge[v]:
            if nv == p:
                continue
            st.append((v, nv, d+1))
    return ret

ans = n 
if k % 2 == 0:
    for i in range(n):
        ret = dfs(-1, i, 0)
        ans = min(ans, ret)
else:
    for u, v in uv:
        ret = dfs(u, v, 0) + dfs(v, u, 0)
        ans = min(ans, ret)

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

n, k = map(int, input().split())
radius = k // 2
edge = [[] for _ in range(n)]
uv = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
    uv.append((a, b))

def dfs(p, v, d):
    ret = 0
    for nv in edge[v]:
        if nv == p:
            continue
        ret += dfs(v, nv, d+1)
    if d > radius:
        return ret + 1
    else:
        return ret

ans = n 
if k % 2 == 0:
    for i in range(n):
        ret = dfs(-1, i, 0)
        ans = min(ans, ret)
else:
    for u, v in uv:
        ret = dfs(u, v, 0) + dfs(v, u, 0)
        ans = min(ans, ret)

print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    edge = [[]for _ in range(N)]
    for _ in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    ans = inf
    if K&1: 
        for a,l in enumerate(edge):
            for b in l:
                res = 0
                q = [a,b]
                visited = set(q)
                for step in range(N-1):
                    if step*2 > (K-1):
                        res += len(q)
                    tmp = []
                    while q:
                        v = q.pop()
                        visited.add(v)
                        for u in edge[v]:
                            if u in visited:
                                continue
                            visited.add(u)
                            tmp.append(u)
                    q = tmp

                ans = min(res, ans)

    else: 
        for center in range(N):
            res = 0
            q = [center]
            visited = set()
            for step in range(N-1):
                tmp = []
                if step*2 > K:
                    res += len(q)
                while q:
                    v = q.pop()
                    if v in visited:
                        continue
                    visited.add(v)
                    for u in edge[v]:
                        if u in visited:
                            continue

                        tmp.append(u)
                q = tmp
            ans = min(res, ans)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N, K, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

def solve(a, b):
    D = [-1] * (N + 1)

    if a == b:
        Q = deque([a])
        r = K // 2
        D[a] = 0
    else:
        Q = deque([a, b])
        r = (K - 1) // 2
        D[a] = D[b] = 0

    cnt = len(Q)
    while Q:
        v = Q.popleft()

        d = D[v] + 1
        if d > r:
            break

        for u in E[v]:
            if D[u] == -1:
                cnt += 1
                D[u] = d
                Q.append(u)

    return N - cnt


if K % 2 == 1:
    print(min(solve(a, b) for a, b in zip(*[iter(AB)] * 2)))
else:
    print(min(solve(a, a) for a in range(1, N + 1)))

Solution (Python):
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N, K = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append(b)
  e[b].append(a)
d = [[N for _ in range(N + 1)] for _ in range(N + 1)]
for s in range(1, N + 1):
  Q = dq([s])
  d[s][s] = 0
  while len(Q):
    p = Q.popleft()
    for q in e[p]:
      if d[s][q] > d[s][p] + 1:
        d[s][q] = d[s][p] + 1
        Q.append(q)
vis = set()
table = [[0] * (N + 1) for _ in range(N + 1)]
lntable = [0] * (N + 1)
for i in range(1, N + 1):
  for j in range(1, N + 1):
    if d[i][j] > K:
      table[i][j] = 1
      lntable[i] += 1
while True:
  t = 0
  for i in range(1, N + 1):
    if i in vis: continue
    if lntable[i] > lntable[t]: t = i
  if t == 0: break
  for i in range(1, N + 1):
    if table[i][t] == 1:
      table[i][t] = 0
      lntable[i] -= 1
  vis.add(t)
print(len(vis))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,K = map(int,readline().split())
m = map(int,read().split())
AB = list(zip(m,m))

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

def F(a,b,K):
    INF = 10 ** 9
    if a == b:
        
        q = deque([a])
        r = K // 2
    else:
        
        q = deque([a,b])
        r = (K-1)//2
    dist = [INF] * (N+1)
    for x in q:
        dist[x] = 0
    pop = q.popleft; append = q.append
    cnt = len(q)
    while q:
        v = pop()
        dw = dist[v] + 1
        if dw > r:
            break
        for w in graph[v]:
            if dist[w] == INF:
                cnt += 1
                dist[w] = dw
                append(w)
    return N - cnt

if K & 1:
    answer = min(F(a,b,K) for a,b in AB)
else:
    answer = min(F(a,a,K) for a in range(1,N+1))
print(answer)

Solution (Python):
N,K=map(int,input().split())
L=[[]for i in range(N+1)]
l=[]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    l.append([a,b])
ans=N
if K%2==0:
    for i in range(1,N+1):
        C=[10000 for i in range(N+1)]
        Q=[[i,0]]
        cnt=0
        for q in range(10000):
            if q==len(Q):
                break
            if C[Q[q][0]]==10000:
                C[Q[q][0]]=Q[q][1]
                cnt+=1
                if Q[q][1]<K//2:
                    for k in L[Q[q][0]]:
                        if C[k]==10000:
                            Q.append([k,Q[q][1]+1])
        if N-cnt<ans:
            ans=N-cnt
        
    print(max(0,ans))
else:
    if K==1:
        print(N-2)
        exit()
    for a,b in l:
        C1=[10000 for i in range(N+1)]
        C2=[10000 for i in range(N+1)]
        X=[[a,0]]
        for q in range(10000):
            if q==len(X):
                break
            if C1[X[q][0]]==10000:
                C1[X[q][0]]=X[q][1]
                if X[q][1]<(K-1)//2:
                    for k in L[X[q][0]]:
                        if C1[k]==10000:
                            X.append([k,X[q][1]+1])
        Y=[[b,0]]
        for q in range(10000):
            if q==len(Y):
                break
            if C2[Y[q][0]]==10000:
                C2[Y[q][0]]=Y[q][1]
                if Y[q][1]<(K-1)//2:
                    for k in L[Y[q][0]]:
                        if C2[k]==10000:
                            Y.append([k,Y[q][1]+1])
        cnt=0
        for x in range(1,N+1):
            if C1[x]<=(K-1)//2 or C2[x]<=(K-1)//2:
                cnt+=1
        
        if N-cnt<ans:
            ans=N-cnt
    print(max(0,ans))

Solution (Python):
n,k = [int(i) for i in input().split()]
edges = [[int(i)-1 for i in input().split()] for j in range(n-1)]

node = [[] for _ in range(n)]
for edge in edges:
    node[edge[0]].append(edge[1])
    node[edge[1]].append(edge[0])

M = 0
for i in range(n):
    count = 1
    que = []
    check = [False]*n
    if k%2==0:
        check[i] = True
        que.append(i)
    elif i!=n-1:
        check[edges[i][0]]=True
        check[edges[i][1]]=True
        que.append(edges[i][0])
        que.append(edges[i][1])
        count = 2
    for j in range(k//2):
        newque = []
        while len(que)!=0:
            q = que.pop()
            for l in node[q]:
                if check[l]:
                    continue
                newque.append(l)
                check[l] = True
                count += 1
        que = newque
    M = max(M,count)
print(n-M)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


n,k = map(int, input().split())
G = [[] for i in range(n)]
edges = []
for i in range(n-1):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    G[b].append(a)
    edges.append((a,b))

cnt = [0]
def search(cur, prev, depth, k):
    if depth > k:
        cnt[0] += 1
    for to in G[cur]:
        if to != prev:
            search(to, cur, depth+1, k)


ans = float("inf")

if k % 2 == 0:
    for i in range(n):
        cnt = [0]
        search(i, -1, 0, k//2)
        ans = min(ans, cnt[0])

else:
    for a, b in edges:
        cnt = [0]
        search(a, b, 0, k//2)
        search(b, a, 0, k//2)
        ans = min(ans, cnt[0])

print(ans)

Solution (Python):
from collections import deque

n, k = map(int, input().split())
graph = [[] for _ in range(n+1)]
ab_list = []
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    ab_list.append((a, b))

ans = 2000
max_distance = k // 2

if k % 2 == 0:
    for i in range(1, n+1):
        extra_node_cnt = 0
        q = deque()
        q.append((i, 0))
        seen = [0]*(n+1)
        seen[i] = 1
        while q:
            node, distance = q.popleft()
            if distance > max_distance:
                extra_node_cnt += 1
            for neighor_node in graph[node]:
                if seen[neighor_node] == 0:
                    seen[neighor_node] = 1
                    q.append((neighor_node, distance + 1))
        ans = min(ans, extra_node_cnt)
else:
    for now_node, now_neighbor in ab_list:
        extra_node_cnt = 0
        q = deque()
        q.append((now_node, 0))
        seen = [0]*(n+1)
        seen[now_node] = 1
        seen[now_neighbor] = 1
        while q:
            node, distance = q.popleft()
            if distance > max_distance:
                extra_node_cnt += 1
            for neighor_node in graph[node]:
                if seen[neighor_node] == 0:
                    seen[neighor_node] = 1
                    q.append((neighor_node, distance + 1))
        q = deque()
        q.append((now_neighbor, 0))
        seen = [0]*(n+1)
        seen[now_node] = 1
        seen[now_neighbor] = 1
        while q:
            node, distance = q.popleft()
            if distance > max_distance:
                extra_node_cnt += 1
            for neighor_node in graph[node]:
                if seen[neighor_node] == 0:
                    seen[neighor_node] = 1
                    q.append((neighor_node, distance + 1))
        ans = min(ans, extra_node_cnt)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,K = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

def count_nbd(x,R,parent):
    
    
    count = 0
    visited = [False] * (N+1)
    visited[x] = True
    visited[parent] = True
    count += 1
    q = [x]
    for _ in range(R):
        qq = []
        for y in q:
            for z in graph[y]:
                if visited[z]:
                    continue
                visited[z] = True
                qq.append(z)
                count += 1
        q = qq
    return count

if K&1:
    
    R = (K-1)//2
    x = max(count_nbd(x,R,y) + count_nbd(y,R,x) for x,y in AB)
else:
    
    R = K//2
    x = max(count_nbd(x,R,0) for x in range(1,N+1))

answer = N-x
print(answer)

Solution (Python):
import collections

n,k=map(int,input().split())
g=[[] for _ in range(n+1)]
e=[]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
  e.append((a,b))
ans=0
if k%2==0:
  for i in range(1,n+1):
    tmp=0
    checked=[0]*(n+1)
    checked[i]=1
    q=collections.deque()
    q.append((i,0))
    while len(q)!=0:
      v,d=q.popleft()
      if d<=k//2:
        tmp+=1
      else:
        break
      for u in g[v]:
        if checked[u]==0:
          checked[u]=1
          q.append((u,d+1))
    ans=max(ans,tmp)
  print(n-ans)
if k%2==1:
  for v1,v2 in e:
    tmp=0
    checked=[0]*(n+1)
    checked[v1]=1
    checked[v2]=1
    q=collections.deque()
    q.append((v1,0))
    while len(q)!=0:
      v,d=q.popleft()
      if d<=k//2:
        tmp+=1
      else:
        break
      for u in g[v]:
        if checked[u]==0:
          checked[u]=1
          q.append((u,d+1))
    checked=[0]*(n+1)
    checked[v1]=1
    checked[v2]=1
    q=collections.deque()
    q.append((v2,0))
    while len(q)!=0:
      v,d=q.popleft()
      if d<=(k-1)//2:
        tmp+=1
      else:
        break
      for u in g[v]:
        if checked[u]==0:
          checked[u]=1
          q.append((u,d+1))
    ans=max(ans,tmp)
  print(n-ans)

Solution (Python):
n, k = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

def bfs(start, x):
	vis = [-1 for _ in range(n)]
	vis[start] = 0
	s = [start]
	cnt = 0
	while s:
		l = s.pop()
		cnt += 1
		if vis[l] < x:
			for c in adj[l]:
				if vis[c] < 0:
					s.append(c)
					vis[c] = vis[l] + 1
	return n - cnt

def bfs2(start, nxt, x):
	vis = [-1 for _ in range(n)]
	vis[start] = 0
	vis[nxt] = 0
	s = [start, nxt]
	cnt = 0
	while s:
		l = s.pop()
		cnt += 1
		if vis[l] < x:
			for c in adj[l]:
				if vis[c] < 0:
					s.append(c)
					vis[c] = vis[l] + 1
	return n - cnt

ans = n-2
if k%2 == 0:
	for i in range(n):
		ans = min(ans, bfs(i, k//2))
else:
	for i in range(n):
		for j in adj[i]:
			ans = min(ans, bfs2(i, j, k//2))

print(ans)

Solution (Python):


import sys
from collections import defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, k = LI()

    G = defaultdict(list)
    AB = [LI_() for _ in range(n - 1)]
    for a, b in AB:
        G[a].append(b)
        G[b].append(a)

    def DFS(ss: list, t: int):
        q = deque()
        for s in ss:
            q.append((s, 0))
        visited = [0] * n
        visited[ss[0]] = visited[ss[-1]] = 1
        while q:
            v, d = q.pop()
            if d >= t:
                continue
            for to in G[v]:
                if visited[to]:
                    continue
                visited[to] = 1
                q.append((to, d + 1))
        
        return n - sum(visited)

    
    
    
    
    res = INF
    if k % 2:
        for a, b in AB:
            res = min(res, DFS([a, b], (k - 1) // 2))
    else:
        for i in range(n):
            res = min(res, DFS([i], k // 2))

    return res


print(main())