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: Wrong Answer

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 = [[] 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%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)

Submission status: Wrong Answer

Solution code:
import collections
N,K=map(int,input().strip().split())
AB=[]
for _ in range(N-1):
    t=list(map(int,input().strip().split()))
    AB.append(t)
AB.sort()
ten=[]
kaku=AB[0][0]
for i in range(N-1):
    for x in range(N-1):
        if i==x:
            continue
        if AB[i][0]==AB[x][0]:
            ten.append(AB[x][1])
tenz=[]
tenzz={}
for n in range(N-1):
    for y in ten:
        if y==AB[n][0] or AB[n][0]==kaku:
            continue
        if AB[n][1]==y:
            tenz.append(AB[n][1])
            #tenz.append(AB[n][0])
            tenzz[AB[n][0]]=AB[n][1]

#print(AB,ten,tenz,tenzz)            
if len(tenz)+1<=K:
    print(0)
else:
    l=collections.Counter(tenz)
    print(min(l.values())+1)

Submission status: Wrong Answer

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 = max(search(i[0], i[1], k//2) + search(i[1], i[0], k//2 + 1) , search(i[0], i[1], k//2 + 1) + search(i[1], i[0], k//2))
        if temp > ret:
            ret = temp
        

print(n-ret)

Submission status: Wrong Answer

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

import sys

sys.setrecursionlimit(20000)

l = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-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    
for i in range(n):
    temp = first_search(i, k)
    if temp > ret:
        ret = temp
        
if ret > n:
    print(0)
else:
    print(n-ret)

Submission status: Wrong Answer

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[i]]))

print(ans)

Submission status: Wrong Answer

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

def bfs(graph:list, node:int, start:int, k:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    # kより大きいの距離のものを数える
    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))


# bfs
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]:
            print(st, to)
            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)

Submission status: Wrong Answer

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 bisect import bisect_right

def bfs(graph:list, node:int, start:int, k:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    # kより大きいの距離のものを数える
    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)]
cnt = [0]*n
for _ in range(n-1):
    a,b = li_()
    cnt[a] += 1
    cnt[b] += 1
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))

# leafの数を数える
leaves = []
for i in range(n):
    if cnt[i] == 1:
        leaves.append(i)

# bfs
ans = n
for st in leaves:
    dist, cnt = bfs(adj_list, n, st, k)
    dist.sort()
    ans = min(ans, cnt)
    
print(ans)

Submission status: Wrong Answer

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 bisect import bisect_right

def bfs(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    while que:
        cost, cur_node = que.popleft()
        
        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


# 入力, グラフ作成
n,k = li()
adj_list = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(n-1):
    a,b = li_()
    cnt[a] += 1
    cnt[b] += 1
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))

# leafの数を数える
leaves = []
for i in range(n):
    if cnt[i] == 1:
        leaves.append(i)

# bfs
ans = n
for st in leaves:
    dist = bfs(adj_list, n, st)
    dist.sort()
    ans = min(ans, n - bisect_right(dist,k))
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())

E = np.zeros((N, N), dtype=int)

# Elist = []
for e in range(N-1):
    i, o = map(int, input().split())
    # Elist.append((i-1, o-1))
    E[i-1][o-1] = 1
    E[o-1][i-1] = 1

# print("N, K=", N, K)
# for e in Elist:
#     print(e[0], e[1])

I = np.eye(N, dtype=int)

# print("I=", I)
exit(0)

ie = I
for k in range(K):
    ie = ie + np.matmul(ie, E)
# print("I + IE =", ie)

# withinK = np.count_nonzero(ie, axis=0)
withinK = np.zeros(N, dtype=int)
for i in range(N):
    for j in range(N):
        if ie[i][j] > 0:
            withinK[i] += 1 
# print("withinK=", withinK)
maxBall = np.amax(withinK)
# print("maxBall=", maxBall)
solution = N - maxBall
print(solution)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())

E = np.zeros((N, N), dtype=int)

# Elist = []
for e in range(N-1):
    i, o = map(int, input().split())
    # Elist.append((i-1, o-1))
    E[i-1][o-1] = 1
    E[o-1][i-1] = 1

exit(0)
# print("N, K=", N, K)
# for e in Elist:
#     print(e[0], e[1])

I = np.eye(N, dtype=int)

# print("I=", I)

ie = I
for k in range(K):
    ie = ie + np.matmul(I, E)
# print("I + IE =", ie)

# withinK = np.count_nonzero(ie, axis=0)
withinK = np.zeros(N, dtype=int)
for i in range(N):
    for j in range(N):
        if ie[i][j] > 0:
            withinK[i] += 1 
# print("withinK=", withinK)
maxBall = np.amax(withinK)
# print("maxBall=", maxBall)
solution = N - maxBall
print(solution)

Submission status: Wrong Answer

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 diameter % 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: Wrong Answer

Solution code:
N, K = map(int, input().split())
E = [set() for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)
ma = 0
for i in range(1, N+1):
    L = [i]
    Closed = {i}
    for j in range(K-1):
        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)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)

def get_diamiter(v, parent, dep, edge):
    max_dep, cnt, cnt_prev, ret_v = dep, 1, 0, v
    for e in edge[v]:
        if e != parent:
            cand_dep, cand_cnt, cand_prev, cand_v = get_diamiter(e, v, dep + 1, edge)
            if cand_dep > max_dep:
                max_dep, cnt, cnt_prev, ret_v = cand_dep, cand_cnt, cand_prev, cand_v
            elif cand_dep == max_dep:
                cnt += cand_cnt
                cnt_prev += cand_prev
    return max_dep, cnt, (1 if dep + 1 == max_dep else cnt_prev), ret_v

def remove(v, edge):
    for row in edge:
        if v in row:
            row.remove(v)

def main(N, K, edge):
    v = 0
    ans = 0
    while True:
        _, _, _, v = get_diamiter(v, -1, 0, edge)
        d, c1, p1, v1 = get_diamiter(v, -1, 0, edge)
        if d <= K:
            break
        _, c2, p2, v2 = get_diamiter(v1, -1, 0, edge)
        if c1 < c2 or (c1 == c2 and p1 < p2):
            remove(v1, edge)
            v = v2
        else:
            remove(v2, edge)
            v = v1
        ans += 1
    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)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)

def get_diamiter(v, parent, dep, edge):
    max_dep, cnt, cnt_prev, ret_v = dep, 1, 0, v
    for e in edge[v]:
        if e != parent:
            cand_dep, cand_cnt, cand_prev, cand_v = get_diamiter(e, v, dep + 1, edge)
            if cand_dep > max_dep:
                max_dep, cnt, cnt_prev, ret_v = cand_dep, cand_cnt, cand_prev, cand_v
            elif cand_dep == max_dep:
                cnt += cand_cnt
                cnt_prev += cand_prev
    return max_dep, cnt, (1 if dep + 1 == max_dep else cnt_prev), ret_v

def remove(v, edge):
    for row in edge:
        if v in row:
            row.remove(v)

def main(N, K, edge):
    ans = 0
    _, _, _, v = get_diamiter(0, -1, 0, edge)
    while True:
        d, c1, p1, v1 = get_diamiter(v, -1, 0, edge)
        if d <= K:
            break
        _, c2, p2, v2 = get_diamiter(v1, -1, 0, edge)
        if c1 < c2 or (c1 == c2 and p1 < p2):
            remove(v1, edge)
            v = v2
        else:
            remove(v2, edge)
            v = v1
        ans += 1
    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)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)

def get_diamiter(v, parent, dep, edge):
    max_dep, cnt, cnt_prev, ret_v = dep, 1, 0, v
    for e in edge[v]:
        if e != parent:
            cand_dep, cand_cnt, cand_prev, cand_v = get_diamiter(e, v, dep + 1, edge)
            if cand_dep > max_dep:
                max_dep, cnt, cnt_prev, ret_v = cand_dep, cand_cnt, cnt_prev, cand_v
            elif cand_dep == max_dep:
                cnt += cand_cnt
                cnt_prev += cand_prev
    return max_dep, cnt, (1 if dep + 1 == max_dep else cnt_prev), ret_v

def remove(v, edge):
    for row in edge:
        if v in row:
            row.remove(v)

def main(N, K, edge):
    ans = 0
    _, _, _, v = get_diamiter(0, -1, 0, edge)
    while True:
        d, c1, p1, v1 = get_diamiter(v, -1, 0, edge)
        if d <= K:
            break
        _, c2, p2, v2 = get_diamiter(v1, -1, 0, edge)
        if c1 < c2 or (c1 == c2 and p1 < p2):
            remove(v1, edge)
            v = v2
        else:
            remove(v2, edge)
            v = v1
        ans += 1
    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)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000)

def get_diamiter(v, parent, dep, edge):
    max_dep, cnt, ret_v = dep, 1, v
    for e in edge[v]:
        if e != parent:
            cand_dep, cand_cnt, cand_v = get_diamiter(e, v, dep + 1, edge)
            if cand_dep > max_dep:
                max_dep, cnt, ret_v = cand_dep, cand_cnt, cand_v
            elif cand_dep == max_dep:
                cnt += cand_cnt
    return max_dep, cnt, ret_v

def remove(v, edge):
    for row in edge:
        if v in row:
            row.remove(v)

def main(N, K, edge):
    ans = 0
    _, _, v = get_diamiter(0, -1, 0, edge)
    while True:
        d, c1, v1 = get_diamiter(v, -1, 0, edge)
        if d <= K:
            break
        _, c2, v2 = get_diamiter(v1, -1, 0, edge)
        if c1 < c2:
            remove(v1, edge)
            v = v2
        else:
            remove(v2, edge)
            v = v1
        ans += 1
    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)

Submission status: Wrong Answer

Solution code:
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) + 1)
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: Wrong Answer

Solution code:
from collections import deque
N, K = map(int, input().split())
G = [[] for i 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)

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(N-1)
D = bfs0(D[0])

C = {e for e in D}

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

memo = {}
def bfs(s, rest):
    if rest == 0:
        return 1
    if (s, rest) in memo:
        return memo[s, rest]

    que = deque()
    dist = {s: rest}
    for v in G[s]:
        if v in C:
            continue
        dist[v] = rest-1
        if rest > 1:
            que.append(v)

    while que:
        v = que.popleft()
        for w in G[v]:
            if w in dist:
                continue
            dist[w] = r = dist[v]-1
            if r:
                que.append(w)
    memo[s, rest] = res = len(dist)
    return res

ans = 0
for i in range(l-K):
    cnt = sum(bfs(D[i+j], min(j, K-j)) for j in range(K+1))
    ans = max(ans, cnt)
print(N - ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, K = map(int, input().split())
G = [[] for i 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)

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)

memo = {}
def bfs(s, rest):
    if rest == 0:
        return 1
    if (s, rest) in memo:
        return memo[s, rest]

    que = deque()
    dist = {s: rest}
    for v in G[s]:
        if v in C:
            continue
        dist[v] = rest-1
        if rest > 1:
            que.append(v)

    while que:
        v = que.popleft()
        for w in G[v]:
            if w in dist:
                continue
            dist[w] = r = dist[v]-1
            if r:
                que.append(w)
    memo[s, rest] = res = len(dist)
    return res

ans = 0
for i in range(l-K):
    cnt = sum(bfs(D[i+j], min(j, K-j)) for j in range(K+1))
    ans = max(ans, cnt)
print(N - ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, K = map(int, input().split())
G = [[] for i 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)

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:
    print(0)
    exit(0)

memo = {}
def bfs(s, rest):
    if rest == 0:
        return 1
    if (s, rest) in memo:
        return memo[s, rest]

    que = deque()
    dist = {s: rest}
    for v in G[s]:
        if v in C:
            continue
        dist[v] = rest-1
        if rest > 1:
            que.append(v)

    while que:
        v = que.popleft()
        for w in G[v]:
            if w in dist:
                continue
            dist[w] = r = dist[v]-1
            if r:
                que.append(w)
    memo[s, rest] = res = len(dist)
    return res

ans = 0
for i in range(l-K):
    cnt = sum(bfs(D[i+j], min(j, K-j)) for j in range(K+1))
    ans = max(ans, cnt)
print(N - ans)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,k]=i2()
e=[[] for i in range(n)]
for i in range(n-1):
 [a,b]=i2()
 e[a-1].append(b-1)
 e[b-1].append(a-1)

import sys
sys.setrecursionlimit(10000)

def dfs(v,d):
   global c
   for i in range(len(e[v])):
      if d[e[v][i]]==-1:
         d[e[v][i]]=d[v]+1
         if d[e[v][i]]>=k:c+=1
         dfs(e[v][i],d)
         
         
   
cc=float("inf")
for i in range(n):
  c=0
  d=[-1 for j in range(n)]
  d[i]=0
  dfs(i,d)
  cc=min(cc,c)
print(cc)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
branch = dict()
for i in range(1,n+1):
	branch[i] = []
a = []
b = []
for i in range(n-1):
	atemp,btemp = map(int,input().split())
	branch[atemp].append(btemp)
	branch[btemp].append(atemp)
	a.append(atemp)
	b.append(btemp)

if k%2 == 0:
	ans = []
	for i in range(1,n+1):
		q = [i]
		arrival = [0 for i in range(n+1)]
		arrival[i] = 1
		while len(q) >= 1:
			for e in range(len(branch[q[0]])):
				if arrival[branch[q[0]][e]] == 0:
					q.append(branch[q[0]][e])
					arrival[branch[q[0]][e]] = arrival[q[0]]+1
			q.pop(0)
		counter = 0
		for e in range(1,n+1):
			if arrival[e] > k//2+1:
				counter += 1
		ans.append(counter)
	print(min(ans))

else:
	ans1 = []
	ans2 = []
	for i in range(n-1):
		q1 = [a[i]]
		q2 = [b[i]]
		arrival1 = [0 for i in range(n+1)]
		arrival2 = [0 for i in range(n+1)]
		
		while len(q1) >= 1:
			for e in range(len(branch[q1[0]])):
				if arrival1[branch[q1[0]][e]] == 0:
					q1.append(branch[q1[0]][e])
					arrival1[branch[q1[0]][e]] = arrival1[q1[0]]+1
			q1.pop(0)
		counter = 0
		for e in range(1,n+1):
			if arrival1[e] > k//2+1:
				counter += 1
		ans1.append(counter)

		while len(q2) >= 1:
			for e in range(len(branch[q2[0]])):
				if arrival2[branch[q2[0]][e]] == 0:
					q2.append(branch[q2[0]][e])
					arrival2[branch[q2[0]][e]] = arrival2[q2[0]]+1
			q2.pop(0)
		counter = 0
		for e in range(1,n+1):
			if arrival2[e] > k//2+1:
				counter += 1
		ans2.append(counter)
	
	ans = []
	for e in range(n-1):
		if ans1[e] <= ans2[e]:
			ans.append(ans1[e])
		else:
			ans.append(ans2[e])
	print(min(ans))

Submission status: Wrong Answer

Solution code:
o=lambda:map(int,raw_input().split());r=range;a=10**5
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]
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(n):
  for j in e[i]:
   if i<j:l=[0]*n;U(i,j);a=min(a,U(j,i))
else:
 for i in r(n):l=[0]*n;a=min(a,U(i,-1))
print a

Submission status: Wrong Answer

Solution code:
o=lambda:map(int,raw_input().split());r=range;a=10**5
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]
def U(x,f):
 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(n):
  for j in e[i]:
   if i<j:l=[0]*n;U(i,j);a=min(a,U(j,i))
else:
 for i in r(n):l=[0]*n;a=min(a,U(i,i))
print a

Submission status: Wrong Answer

Solution code:
o=lambda:map(int,raw_input().split());T,F=True,False;r=range;a=10**5
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]
def U(x,f):
 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 r(n):
  for j in e[i]:
   if i<j:l=[F]*n;U(i,j);a=min(a,U(j,i))
else:
 for i in r(n):l=[F]*n;a=min(a,U(i,i))
print a

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dfs1(s,c,cnt):
    visited[s]=1
    for i in v[s]:
        if visited[i]==0:
            d[c][i]=d[c][s]+1
            if k%2==0 and d[c][i]>k/2:
                cnt+=1
            if k%2==1 and d[c][i]>(k-1)/2:
                cnt+=1
            cnt=dfs1(i,c,cnt)
    return cnt

def dfs2(c1,c2,cnt):
    visited[c2]=1
    cnt+=dfs1(c1,c1,cnt)
    cnt+=dfs1(c2,c2,cnt)
    return cnt

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=1000000
    for i in xrange(n):
        cnt=0
        visited=[0]*n
        cnt=dfs1(i,i,cnt)
        min_del=min(min_del,cnt)
    print(min_del)
else:
    min_del=1000000
    for i,j in e:
        cnt=0
        visited=[0]*n
        d=[[0]*n for _ in xrange(n)]
        cnt=dfs2(i,j,cnt)
        min_del=min(min_del,cnt)
    print(min_del)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(b,h,dist,E,rad,ne):
	cnt = 1
	for nxt in E[h]:
		if nxt == b or nxt == ne:
			continue
		if dist + 1 == rad:
			cnt += 1
		else:
			cnt += rad_reach(h,nxt,dist+1,E,rad,ne)
	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,-1))
	else:
		for c1,c2 in pairs:
			ans = min(ans,N-rad_reach(-1,c1,0,E,rad,c2)-rad_reach(-1,c2,0,E,rad,c1))
	print ans
solve()