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 = sys.stdin.readline
n,k = map(int,input().split())
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append((a-1,b-1))

def f(x,y,c):
    global tmp
    c += 1
    for e in edge[x]:
        if e == y:
            continue
        if c > d:
            tmp +=1
        f(e,x,c)

sys.setrecursionlimit(4100000)

if k % 2 == 0:
    d = k//2
    ass = 2001
    for i in range(n):
        tmp = 0
        f(i,-1,0)
        ass = min(ass,tmp)
    print(ass)
else:
    d = (k-1)//2
    ass = 2001
    for e1 in alledge:
        tmp = 0
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        ass = min(ass,tmp)
    print(ass)

Solution (Python):
import sys

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

def f(x,y,c):
    global tmp
    c += 1
    for e in edge[x]:
        if e == y:
            continue
        if c > d:
            tmp +=1
        f(e,x,c)

sys.setrecursionlimit(4100000)

if k % 2 == 0:
    d = k//2
    ass = 2001
    for i in range(n):
        tmp = 0
        f(i,-1,0)
        ass = min(ass,tmp)
    print(ass)
else:
    d = (k-1)//2
    ass = 2001
    for e1 in alledge:
        tmp = 0
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        ass = min(ass,tmp)
    print(ass)

Solution (Python):
import copy

N, K = (int(i) for i in input().split())

G = [[] for i in range(N)]
E = []
for i in range(N-1):
    A, B = (int(i) for i in input().split())
    E.append((A-1, B-1))
    G[A-1].append(B-1)
    G[B-1].append(A-1)

def DFS(u, n, G):
    q = [u]
    v = [0]*N
    d = [0]*N
    while q:
        u1 = q.pop()
        v[u1] = 1
        if d[u1] < n:
            for u2 in G[u1]:
                if not v[u2]:
                    d[u2] = d[u1] + 1
                    q.append(u2)
    return sum(v)

def DFS_E(u, uu, n, G):
    q = [u, uu]
    v = [0]*N
    d = [0]*N
    while q:
        u1 = q.pop()
        v[u1] = 1
        if d[u1] < n:
            for u2 in G[u1]:
                if not v[u2] and u2 != u:
                    d[u2] = d[u1] + 1
                    q.append(u2)
    return sum(v)


if K % 2 == 0:
    ans = 0
    for v in range(N):
        ans = max(ans, DFS(v, K//2, G))
    print(N-ans)
else:
    ans = 0
    for u, v in E:
        ans = max(ans, DFS_E(u,v,(K-1)//2,G))
    print(N-ans)

Solution (Python):
from collections import deque
N,K=map(int,input().split())
node=[0]*N
edge={}
G=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  edge[(a-1,b-1)]=0
  G[a-1].append(b-1)
  G[b-1].append(a-1)
if K%2:
  for a,b in edge.keys():
    visited=[False]*N
    stack=deque([(a,0),(b,0)])
    visited[a],visited[b]=True,True
    while stack:
      n,c=stack.popleft()
      if c>K//2:
        break
      edge[(a,b)]+=1
      for s in G[n]:
        if not visited[s]:
          stack.append((s,c+1))
          visited[s]=True
  print(N-max(edge.values()))
else:
  for a in range(N):
    visited=[False]*N
    stack=deque([(a,0)])
    visited[a]=True
    while stack:
      n,c=stack.popleft()
      if c>K//2:
        break
      node[a]+=1
      for s in G[n]:
        if not visited[s]:
          stack.append((s,c+1))
          visited[s]=True
  print(N-max(node))

Solution (Python):
from collections import deque
import math
N,K=map(int,input().split())
table=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].append(b)
    table[b].append(a)


t=K//2
s=K%2
def dfs(i):
    visit=[-1]*N
    h=deque()
    h.append(i)
    visit[i]=0
    num=0
    a=0
    while h:
        x=h.popleft()
        for y in table[x]:
            if visit[y]==-1:
                visit[y]=visit[x]+1
                h.append(y)
    for k in range(N):
        if 0<=visit[k]<=t:
            num+=1
    
    return num

def dfs2(i,j):
    visit=[-1]*N
    h=deque()
    h.append(i)
    h.append(j)
    visit[i]=0
    visit[j]=0
    num=0
    while h:
        x=h.popleft()
        for y in table[x]:
            if visit[y]==-1:
                visit[y]=visit[x]+1
                h.append(y)
    for k in range(N):
        if 0<=visit[k]<=t:
            num+=1
    
    return num
if s==0:
    ans=0
    for i in range(N):
        ans=max(ans,dfs(i))
    print(N-ans)
elif s==1:
    ans=0
    for i in range(N):
        for j in table[i]:
            if j>i:
                ans=max(ans,dfs2(i,j))
    print(N-ans)

Solution (Python):
from collections import deque
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans,c = [[] for i in range(n)],[[] for i in range(n)],n,0
for i,j in b:
	x[i].append(j)
	x[j].append(i)
def f(s):
	for i in range(n):
		q,v = deque(),[1]*n
		v[i] = 0
		for j in x[i]:
			q.append((j,1,j))
			d[i].append(j)
			v[j] = 0
		while q:
			p = q.pop()
			if p[1]<s:
				for j in x[p[0]]:
					if v[j]:
						q.append((j,p[1]+1,p[2]))
						d[i].append(p[2])
						v[j] = 0
if k>n//2:
	for i in x: c = max(len(i),c)
if n-c+1<=k: ans = 0
elif k==1: ans = n-2
else:
	f(k//2)
	if k%2:
		for i,j in b: ans = min(ans,n-len(d[i])-len(d[j])+d[i].count(j)+d[j].count(i)-2)
	else:
		for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)

Solution (Python):
n, k = map(int, input().split())

import sys

sys.setrecursionlimit(2000)

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

def first_search(first, depth):
    record = 0
    for i in l[first]:
        temp = search(first, i, depth-1)
        if record < temp:
            record = temp
    return record + 1

def search(before, now, depth):
    if depth <= 0:
        return 1
    else:
        ans = 1
        for i in l[now]:
            if before != i:
                ans += search(now, i, depth-1)
        return ans

ret = 0
if k%2 == 0:
    for i in range(n):
        temp = search(-1, i, k//2)
        if temp > ret:
            ret = temp
else:           
    for i in e:
        temp = search(i[0], i[1], k//2) + search(i[1], i[0], k//2)
        if temp > ret:
            ret = temp
        

print(n-ret)

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque
from collections import defaultdict

def bfs(graph:list, start:int) -> list:
    
    node = len(graph)
    dist = [None]*node
    
    
    dist[start] = 0
    que = deque([(0,start)])
    
    
    
    while que:
        cost, cur_node = que.popleft()

        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] is not None:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist
  

n,k = li()
adj_list = [[] for _ in range(n)]
edges = []
for _ in range(n-1):
    a,b = li_()
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))
    edges.append((a,b))

ans = n
dists = []
for i in range(n):
    dists.append(bfs(adj_list, i))

if k%2:
    for a,b in edges:
        ans = min(ans, sum([min(d1,d2) > (k-1)//2 for d1,d2 in zip(dists[a], dists[b])]))
    

else:
    for st in range(n):
        ans = min(ans, sum([d > k//2 for d in dists[st]]))

print(ans)

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque
from collections import defaultdict

def bfs(graph:list, start:int) -> list:
    
    node = len(graph)
    dist = [None]*node
    
    
    dist[start] = 0
    que = deque([(0,start)])
    
    
    
    while que:
        cost, cur_node = que.popleft()

        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] is not None:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist
  

n,k = li()
adj_list = [[] for _ in range(n)]
edges = []
for _ in range(n-1):
    a,b = li_()
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))
    edges.append((a,b))

ans = n

if k%2:
    for a,b in edges:
        dist1 = bfs(adj_list, a)
        dist2 = bfs(adj_list, b)
        ans = min(ans, sum([min(d1,d2) > (k-1)//2 for d1,d2 in zip(dist1, dist2)]))
    

else:
    for st in range(n):
        dist = bfs(adj_list, st)
        ans = min(ans, sum([d > k//2 for d in dist]))

print(ans)

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def bfs(graph:list, node:int, start:int, k:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    que = deque([(0,start)])
    
    
    
    cnt = 0
    while que:
        cost, cur_node = que.popleft()
        
        if cost > k:
            cnt += 1
        
        
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist,cnt



n,k = li()
adj_list = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = li_()
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))



ans = n
if k%2 == 0:
    for st in range(n):
        _, cnt = bfs(adj_list, n, st, k//2)
        ans = min(ans, cnt)
        
else:
    for st in range(n):
        for cost, to in adj_list[st]:
            if to <= st:
                continue
            
            dist1, _ = bfs(adj_list, n, st, (k-1)//2)
            dist2, _ = bfs(adj_list, n, to, (k-1)//2)
            cnt = 0
            
            for d1, d2 in zip(dist1, dist2):
                if min(d1,d2) > (k-1)//2:
                    cnt += 1
                    
            ans = min(ans, cnt)
        
print(ans)

Solution (Python):
from collections import deque
N,K = map(int,input().split())
es = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
tr = [[] for i in range(N)]
for a,b in es:
    tr[a].append(b)
    tr[b].append(a)

def reachable_points(root_v, cant_visit_v):
    visited = [0] * N
    visited[root_v] = visited[cant_visit_v] = 1
    q = deque([(root_v,0)])
    ret = 0
    while q:
        v,dep = q.popleft()
        if dep == K//2: break
        for to in tr[v]:
            if visited[to]: continue
            ret += 1
            q.append((to,dep+1))
            visited[to] = 1
    return ret

def reachable_edges(root_e):
    a,b = es[root_e]
    return reachable_points(a,b) + reachable_points(b,a)

if K%2:
    ans = N
    for center_e in range(N-1):
        ans = min(ans, N - 2 - reachable_edges(center_e))
    print(ans)
else:
    ans = N
    for center_v in range(N):
        ans = min(ans, N - 1 - reachable_points(center_v, center_v))
    print(ans)

Solution (Python):
from collections import deque
N,K = map(int,input().split())
es = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
tr = [[] for i in range(N)]
for i,(a,b) in enumerate(es):
    tr[a].append((b,i))
    tr[b].append((a,i))

def reachable_points(root_v, cant_visit_v):
    visited = [0] * N
    visited[root_v] = visited[cant_visit_v] = 1
    q = deque([(root_v,0)])
    ret = 0
    while q:
        v,dep = q.popleft()
        if dep == K//2: break
        for to,_ in tr[v]:
            if visited[to]: continue
            ret += 1
            q.append((to,dep+1))
            visited[to] = 1
    return ret

def reachable_edges(root_e):
    a,b = es[root_e]
    return reachable_points(a,b) + reachable_points(b,a)

if K%2:
    ans = N
    for center_e in range(N-1):
        ans = min(ans, N - 2 - reachable_edges(center_e))
    print(ans)
else:
    ans = N
    for center_v in range(N):
        ans = min(ans, N - 1 - reachable_points(center_v, center_v))
    print(ans)

Solution (Python):
N,K=map(int,input().split())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
d=[[-1 for i in range(N)] for j in range(N)]
for i in range(N):
    q=[i]
    d[i][i]=0
    while(len(q)>0):
        r=q[-1];q.pop()
        for p in G[r]:
            if d[i][p]!=-1:
                continue
            d[i][p]=d[i][r]+1
            q.append(p)

if K%2==0:
    t=[[d[i][j] for i in range(N)] for j in range(N)]
    D=K//2
    ans=[0 for i in range(N)]
    for i in range(N):
        for j in range(N):
            if t[i][j]>D:
                ans[i]+=1
    print(min(ans))
else:
    t=[[min([d[a[i]][j],d[b[i]][j]]) for j in range(N)] for i in range(N-1)]
    ans=[0 for i in range(N-1)]
    D=(K-1)//2
    for i in range(N-1):
        for j in range(N):
            if t[i][j]>D:
                ans[i]+=1
    print(min(ans))

Solution (Python):
from collections import deque

INF = float('inf')

N, K = map(int, input().split())
edges = [list(map(lambda x: int(x) - 1, input().split())) for e in range(N - 1)]

adjL = [[] for v in range(N)]
for a, b in edges:
    adjL[a].append(b)
    adjL[b].append(a)


def bfs(adjList, VCenter, radius):
    numV = len(adjList)

    dist = [INF] * numV
    for v in VCenter:
        dist[v] = 0

    ans = 0
    Q = deque(VCenter)
    while Q:
        vNow = Q.popleft()
        distNow = dist[vNow]

        if distNow > radius: break
        ans += 1

        for v2 in adjList[vNow]:
            if dist[v2] != INF: continue
            dist[v2] = distNow + 1
            Q.append(v2)

    return ans



if K % 2:
    
    VC = edges
    r = (K - 1) // 2
else:
    
    VC = [[v] for v in range(N)]
    r = K // 2

ans = N
for V in VC:
    num = bfs(adjL, V, r)
    ans = min(ans, N - num)

print(ans)

Solution (Python):
from collections import deque

N, K = map(int, input().split())
T = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    E.append([a, b])


def bfs(n):
    visited = [False] * N
    dist = [0] * N
    queue = deque([n])
    while queue:
        node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        for n in T[node]:
            if not visited[n]:
                dist[n] = dist[node] + 1
                queue.appendleft(n)
    return dist


dist = []
for i in range(N):
    dist.append(bfs(i))

ans = float('inf')
if K % 2 == 0:
    for i in range(N):
        ans = min(ans, len([d for d in dist[i] if d > K / 2]))

else:
    for a, b in E:
        ans = min(ans, len([d for d in [min(d1, d2) for d1, d2 in zip(dist[a], dist[b])] if d> (K-1) / 2]))

print(ans)

Solution (Python):
from collections import deque

N, K = map(int, input().split())
T = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    E.append([a, b])


def bfs(n):
    visited = [False] * N
    dist = [0] * N
    queue = deque([n])
    while queue:
        node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        for n in T[node]:
            if not visited[n]:
                dist[n] = dist[node] + 1
                queue.appendleft(n)
    return dist


dist = []
for i in range(N):
    dist.append(bfs(i))

ans = float('inf')
if K % 2 == 0:
    for i in range(N):
        ans = min(ans, len([d for d in dist[i] if d > K / 2]))
else:
    for a, b in E:
        ans = min(ans, len([d for d in [min(d1, d2) for d1, d2 in zip(dist[a], dist[b])] if d > (K-1) / 2]))

print(ans)

Solution (Python):
from collections import deque

N, K = map(int, input().split())
T = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))


def bfs(n):
    visited = [False] * N
    dist = [0] * N
    queue = deque([n])
    while queue:
        node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        for n in T[node]:
            if not visited[n]:
                dist[n] = dist[node] + 1
                queue.appendleft(n)
    return dist


dist = []
for i in range(N):
    dist.append(bfs(i))

ans = float('inf')
if K % 2 == 0:
    
    for i in range(N):
        ans = min(ans, len([d for d in dist[i] if d > K / 2]))
else:
    
    for a, b in E:
        adist = [(1 if min(d1, d2) > (K-1) / 2 else 0) for d1, d2 in zip(dist[a], dist[b])]
        ans = min(ans, sum(adist))

print(ans)

Solution (Python):
from collections import deque

N, K = map(int, input().split())
T = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))


def bfs(n):
    visited = [False] * N
    dist = [0] * N
    queue = deque([n])
    while queue:
        node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        for n in T[node]:
            if not visited[n]:
                dist[n] = dist[node] + 1
                queue.appendleft(n)
    return dist


dist = []
for i in range(N):
    dist.append(bfs(i))

ans = float('inf')
if K % 2 == 0:
    
    for i in range(N):
        ans = min(ans, len(list(filter(lambda x: K / 2 < x, dist[i]))))
else:
    
    for a, b in E:
        adist = [min(d1, d2) for d1, d2 in zip(dist[a], dist[b])]
        ans = min(ans, len(list(filter(lambda x: (K-1) / 2 < x, adist))))

print(ans)

Solution (Python):
from collections import deque

N, K = map(int, input().split())
T = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))


def dfs(n):
    visited = [False] * N
    stack = [[n, 0]]
    longest = [-1, -1]

    while stack:
        node, weight = stack.pop()
        if visited[node]:
            continue
        visited[node] = True
        if longest[1] < weight:
            longest = [node, weight]

        for n in T[node]:
            if not visited[n]:
                stack.append([n, weight + 1])

    return longest


def bfs(n):
    visited = [False] * N
    dist = [0] * N
    queue = deque([n])
    while queue:
        node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        for n in T[node]:
            if not visited[n]:
                dist[n] = dist[node] + 1
                queue.appendleft(n)
    return dist


xn, xw = dfs(0)
yn, yw = dfs(xn)
diameter = yw

d = bfs(0)
ans = float('inf')
if K % 2 == 0:
    
    for i in range(N):
        dist = bfs(i)
        ans = min(ans, len(list(filter(lambda x: K / 2 < x, dist))))
else:
    
    for a, b in E:
        dist1 = bfs(a)
        dist2 = bfs(b)
        dist = [min(d1, d2) for d1, d2 in zip(dist1, dist2)]
        ans = min(ans, len(list(filter(lambda x: (K-1) / 2 < x, dist))))

print(ans)

Solution (Python):
N, K = map(int, input().split())
E = [set() for i in range(N+1)]
Er = []
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)
    Er.append({a, b})
ma = 0
Start = []
if K&1 == 1:
    Start = Er
else:
    Start = [{i} for i in range(1, N+1)]
for st in Start:
    L = list(st)
    Closed = st
    for j in range(K//2):
        S = []
        for l in L:
            S += E[l]
        L = []
        for s in S:
            if s not in Closed:
                L.append(s)
                Closed.add(s)
    ma = max(ma, len(Closed))
print(N-ma)

Solution (Python):
import sys
sys.setrecursionlimit(5000)


def dfs(v, parent, rest, edge):
    ret = 0
    for c in edge[v]:
        if c != parent:
            ret += dfs(c, v, rest - 1, edge)
    return ret + (rest <= 0)


def main(N, K, edge):
    ans = N
    if K % 2 == 0:
        for v in range(N):
            ans = min(ans, sum(dfs(c, v, K // 2, edge) for c in edge[v]))
    else:
        for v in range(N):
            for c in edge[v]:
                ans = min(ans, dfs(v, c, K // 2 + 1, edge) + dfs(c, v, K // 2 + 1, edge))
    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        edge[u].append(v)
        edge[v].append(u)
    main(N, K, edge)

Solution (Python):

from collections import deque
N, K = map(int, input().split())
G = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    E.append((a-1, b-1))

def bfs0(s):
    que = deque()
    prev = [-1]*N
    prev[s] = s
    que.append(s)
    while que:
        v = que.popleft()
        for w in G[v]:
            if prev[w] == -1:
                prev[w] = v
                que.append(w)
    L = []
    while v != s:
        L.append(v)
        v = prev[v]
    L.append(s)
    return L

D = bfs0(0)
D = bfs0(D[0])

C = {e for e in D}

l = len(D)
if l <= K+1:
    print(0)
    exit(0)

def bfs(que, U, K2):
    if K2 == 0:
        return 0
    cnt = 0
    while que:
        v = que.popleft()
        for w in G[v]:
            if U[w] != -1:
                continue
            U[w] = r = U[v] + 1
            cnt += 1
            if r < K2:
                que.append(w)
    return cnt

ans = 0
que = deque()
if K % 2:
    for a, b in E:
        U = [-1]*N
        U[a] = U[b] = 0
        que.append(a)
        que.append(b)
        ans = max(ans, bfs(que, U, K // 2) + 2)
else:
    for i in range(N):
        U = [-1]*N
        U[i] = 0
        que.append(i)
        ans = max(ans, bfs(que, U, K // 2) + 1)
print(N - ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,k = LI()
    e = collections.defaultdict(list)
    t = []
    for _ in range(n-1):
        a,b = LI_()
        e[a].append(b)
        e[b].append(a)
        t.append((a,b))

    r = inf
    q = [0] * n
    k2 = k//2
    if k%2 == 0:
        for i in range(n):
            v = [-1] * n
            v[i] = 0
            q[0] = i
            qi = qe = 0
            while qi <= qe:
                c = q[qi]
                for ni in e[c]:
                    if v[ni] >= 0:
                        continue
                    if v[c] == k2:
                        continue
                    v[ni] = v[c] + 1
                    qe += 1
                    q[qe] = ni
                qi += 1
            tr = n-qe-1
            if r > tr:
                r = tr
    else:
        for i in range(n-1):
            a,b = t[i]
            v = [-1] * n
            v[a] = v[b] = 0
            q[0] = a
            q[1] = b
            qi = 0
            qe = 1
            while qi <= qe:
                c = q[qi]
                for ni in e[c]:
                    if v[ni] >= 0:
                        continue
                    v[ni] = v[c] + 1
                    if v[ni] > k2:
                        continue
                    qe += 1
                    q[qe] = ni
                qi += 1
            tr = n-qe-1
            if r > tr:
                r = tr

    return r

print(main())

Solution (Python):
def dfs(now, d):
    visited[now] = True
    if d == k / 2  : return
    for nx in g[now]:
        if not visited[nx]:
            dfs(nx, d + 1)

n, k = map(int, raw_input().split())
g = [[] for _ in xrange(n)]
for i in xrange(n - 1):
    a, b = map(int, raw_input().split())
    a -= 1; b -= 1;
    g[a].append(b)
    g[b].append(a)
    
ans = n
if k % 2 == 1:
    for i in xrange(n):
        for j in g[i]:
            visited = [False] * n
            visited[i] = True
            visited[j] = True
            dfs(i, 0)
            dfs(j, 0)
            ans = min(ans, n - sum(visited))
    print ans
else:
    for i in xrange(n):
        visited = [False] * n
        visited[i] = True
        dfs(i, 0)
        ans = min(ans, n - sum(visited))
    print ans

Solution (Python):
o=lambda:map(int,raw_input().split());s=9999
n,k=o();r=range(n)
e=[[]for _ in [0]*n]
for _ in [0]*(n-1):a,b=o();e[a-1]+=[b-1];e[b-1]+=[a-1]
def U(x,f):
 if f<n:l[f]=0
 q=[(x,0)]
 while len(q):
  v,c=q.pop(0)
  if c>k/2:break
  l[v]=0
  for w in e[v]:
   if l[w]:q+=[(w,c+1)]
 return n-l.count(0)
if k%2:
 for i in r:
  for j in e[i]:
   if i<j:l=[1]*n;U(i,j);s=min(s,U(j,i))
else:
 for i in r:l=[1]*n;s=min(s,U(i,n))
print s

Solution (Python):
o=lambda:map(int,raw_input().split());s=10**5
n,k=o();r=range(n)
e=[[]for _ in [0]*n]
for _ in [0]*(n-1):a,b=o();e[a-1]+=[b-1];e[b-1]+=[a-1]
def U(x,f):
 if f>=0:l[f]=1
 q=[(x,0)]
 while len(q):
  v,c=q.pop(0)
  if c>k/2:break
  l[v]=1
  for w in e[v]:
   if not l[w]:q+=[(w,c+1)]
 return n-l.count(1)
if k%2:
 for i in r:
  for j in e[i]:
   if i<j:l=[0]*n;U(i,j);s=min(s,U(j,i))
else:
 for i in r:l=[0]*n;s=min(s,U(i,-1))
print s

Solution (Python):
o=lambda:map(int,raw_input().split())
T,F=True,False
n,k=o()
e=[[] for _ in [0]*n]
for _ in [0]*(n-1):a,b=o();e[a-1]+=[b-1];e[b-1]+=[a-1]
a=10**5
def dfs(x,f):
 if f>=0:l[f]=T
 q=[(x,0)]
 while len(q):
  v,c=q.pop(0)
  if c>k/2:break
  l[v]=T
  for w in e[v]:
   if not l[w]:q+=[(w,c+1)]
 return n-l.count(T)
if k%2:
 for i in range(n):
  for j in e[i]:
   if i<j:l=[F]*n;dfs(i,j);a=min(a,dfs(j,i))
else:
 for i in range(n):l=[F]*n;a=min(a,dfs(i,-1))
print a

Solution (Python):
ii=lambda:map(int,raw_input().split())
n,k=ii()
T,F=True,False
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=ii()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
cost=[0]*n
ans=10**5
def dfs(x,f):
    if f>=0:vis[f]=T
    q=[(x,0)]
    while len(q):
        v,c=q.pop(0)
        if c>k/2:break
        cost[v]=c;vis[v]=T
        for w in e[v]:
            if not vis[w]:q+=[(w,c+1)]
    return n-vis.count(T)
if k%2:
    for i in range(n):
        for j in e[i]:
            if i<j:vis=[F]*n;dfs(i,j);ans=min(ans,dfs(j,i))
else:
    for i in range(n):vis=[F]*n;ans=min(ans,dfs(i,-1))
print ans

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(b,h,dist,E,rad):
	cnt = 1
	if dist < rad:
		for nxt in E[h]:
			if nxt == b:
				continue
			cnt += rad_reach(h,nxt,dist+1,E,rad) 
	return cnt
def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [[] for i in xrange(N)]
	for i in xrange(N-1):
		a,b = map(lambda x:int(x)-1,raw_input().split())
		E[a].append(b)
		E[b].append(a)
		pairs.append((a,b))
	ans = N
	rad = K/2
	if K % 2 == 0:
		for c in xrange(N):
			ans = min(ans,N-rad_reach(-1,c,0,E,rad))
	else:
		for c1,c2 in pairs:
			ans = min(ans,N-rad_reach(c2,c1,0,E,rad)-rad_reach(c1,c2,0,E,rad))
	print ans
solve()

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**6)

def bfs1(c):
    visited[c]=1
    q=deque([c])
    while len(q)>0:
        p=q.popleft()
        for i in v[p]:
            if visited[i]==0:
                q.append(i)
                visited[i]=1
                d[c][i]=d[c][p]+1

def bfs2(c1,c2):
    visited[c2]=1
    bfs1(c1)
    bfs1(c2)

n,k=map(int,raw_input().split())
d=[[0]*n for _ in xrange(n)]
v=[[] for _ in xrange(n)]
e=[]
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    v[a].append(b)
    v[b].append(a)
    e.append([a,b])
if k%2==0:
    min_del=2005
    for i in xrange(n):
        cnt=0
        visited=[0]*n
        bfs1(i)
        for j in xrange(n):
            if d[i][j]>k/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)
else:
    min_del=2005
    for i,j in e:
        cnt=0
        visited=[0]*n
        bfs2(i,j)
        for l in xrange(n):
            if d[i][l]>(k-1)/2 or d[j][l]>(k-1)/2:
                cnt+=1
        min_del=min(min_del,cnt)
        d[i]=[0]*n
        d[j]=[0]*n
    print(min_del)

Solution (Python):
from collections import deque
def rad_reach(bfr,h,rest,E):
	cnt = 0
	Q = deque([(bfr,h,rest)])
	while Q:
		cnt += 1
		bfr,h,rest = Q.popleft()
		if rest > 0:
			for nxt in E[h]:
				if nxt == bfr:
					continue
				Q.append((h,nxt,rest-1))
	return cnt
def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [[] for i in xrange(N)]
	for i in xrange(N-1):
		p = map(lambda x:int(x)-1,raw_input().split())
		pairs.append(p)
		E[p[0]].append(p[1])
		E[p[1]].append(p[0])
	ans = N
	rad = K/2
	if K % 2 == 0:
		for c in xrange(N):
			ans = min(ans,N-rad_reach(-1,c,rad,E))
	else:
		for c1,c2 in pairs:
			ans = min(ans,N-rad_reach(c2,c1,rad,E)-rad_reach(c1,c2,rad,E))
	print ans
solve()