Buggy python submission (verdict: Time Limit Exceeded):
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)
for i in x: c = max(len(i),c)
if n-c+1<=k: ans = 0
elif k==1: ans = n-2
else:
	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]<k//2:
				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%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)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
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 = [[] for i in range(n)],[[] for i in range(n)],n
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==1: ans = n-2
elif k%2:
	f((k-1)//2)
	for i in range(n-1):
		d1,d2 = d[b[i][0]],d[b[i][1]]
		ans = min(ans,n-len(d1)-len(d2)+d1.count(b[i][1])+d2.count(b[i][0])-2)
else:
	f(k//2)
	for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
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 = [[] for i in range(n)],[[None]*n for i in range(n)],n
for i,j in b:
	x[i].append(j)
	x[j].append(i)
for i in range(n):
	q,v,d[i][i] = [],[1]*n,(0,-1)
	v[i] = 0
	for j in x[i]:
		q.append((j,1,j))
		d[i][j],v[j] = (1,j),0
	while q:
		p = q.pop()
		for j in x[p[0]]:
			if v[j]:
				q.append((j,p[1]+1,p[2]))
				d[i][j],v[j] = (p[1]+1,p[2]),0
if k%2:
	for i in range(n-1):
		a = n
		for j,j2 in d[b[i][0]]:
			if b[i][1]!=j2 and (k-1)//2>=j: a-=1
		for j,j2 in d[b[i][1]]:
			if b[i][0]!=j2 and (k-1)//2>=j: a-=1
		ans = min(a,ans)
else:
	for i in range(n):
		a = n
		for j,j2 in d[i]:
			if j<=k//2: a-=1
		ans = min(a,ans)
print(ans)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
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 = [[] for i in range(n)],[[None]*n for i in range(n)],n
for i,j in b:
	x[i].append(j)
	x[j].append(i)
for i in range(n):
	q,v,d[i][i] = [],[1]*n,(0,-1)
	v[i] = 0
	for j in x[i]:
		q.append((j,1,j))
		d[i][j],v[j] = (1,j),0
	while q:
		p = q.pop()
		for j in x[p[0]]:
			if v[j]:
				q.append((j,p[1]+1,p[2]))
				d[i][j],v[j] = (p[1]+1,p[2]),0
if k%2:
	for i in range(n-1):
		a = n
		for j,j2 in d[b[i][0]]:
			if b[i][1]!=j2 and (k-1)//2>=j: a-=1
		for j,j2 in d[b[i][1]]:
			if b[i][0]!=j2 and (k-1)//2>=j: a-=1
		ans = min(a,ans)
else:
	for i in range(n): ans = min(ans,n-bisect_left(sorted(d[i]),(k//2+1,0)))
print(ans)

Fixed submission:
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)