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.



Sample input:
6 2
1 2
3 2
4 2
1 6
5 6


Sample output:
2

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding:utf-8

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)

    # 木の性質
    # 直径をdとした時
    # dが偶数ならば，ある頂点vから他の頂点への距離がD/2となる頂点vが存在する
    # dが奇数ならば，ある辺eから他の頂点への距離が(D-1)/2となる辺eが存在する
    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())

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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
    #print(a,num,visit)
    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
    #print(a,num,visit)
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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:
    # 未探索のノードは距離null
    node = len(graph)
    dist = [None]*node
    
    # 始点ノードの距離を0とし、bfsのためのqueueを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    # kより大きいの距離のものを数える
    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))
# kが奇数の時
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])]))
    
# kが偶数の時
else:
    for st in range(n):
        ans = min(ans, sum([d > k//2 for d in dists[st]]))

print(ans)

Submission status: Accepted

Solution code:
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:
    # 未探索のノードは距離null
    node = len(graph)
    dist = [None]*node
    
    # 始点ノードの距離を0とし、bfsのためのqueueを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    # kより大きいの距離のものを数える
    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
# kが奇数の時
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)]))
    
# kが偶数の時
else:
    for st in range(n):
        dist = bfs(adj_list, st)
        ans = min(ans, sum([d > k//2 for d in dist]))

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)
#dia=max([max([d[i][j] for i in range(N)]) for j in range(N)])
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))

Submission status: Accepted

Solution code:
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)

# 頂点の集合VCenterから距離radius以内にある頂点の数を求める
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


# 削除後の「直径Kの木」の中心を全探索する
if K % 2:
    # Kが奇数の場合、全ての辺を試す
    VC = edges
    r = (K - 1) // 2
else:
    # Kが偶数の場合、全ての頂点を試す
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# seishin.py
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)

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1000000)
def calc_dist(b,h,dist,E,D,ne):
	D[dist] += 1
	for nxt in E[h]:
		if nxt == b or nxt == ne:
			continue
		calc_dist(h,nxt,dist+1,E,D,ne) 

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 i in xrange(N):
			D = [0]*N
			calc_dist(-1,i,0,E,D,-1)
			for j in xrange(rad):
				D[rad-j-1] += D[rad-j]
			ans = min(N-D[0],ans)
	else:
		for a,b in pairs:
			D1 = [0]*N
			D2 = [0]*N
			calc_dist(-1,a,0,E,D1,b)
			calc_dist(-1,b,0,E,D2,a)
			for j in xrange(rad):
				D1[rad-j-1] += D1[rad-j]
				D2[rad-j-1] += D2[rad-j]
			ans = min(N-D1[0]-D2[0],ans)
	print ans

solve()