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: Runtime Error

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))
if n==2:
    print(0)
    exit()


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


if k % 2 == 0:
    d = k//2
    res = []
    for i in range(n):
        used = [0]*n
        f(i,-1,0)
        res.append(sum(used))
    print(min(res))
else:
    d = (k-1)//2
    res = []
    for e1 in alledge:
        used = [0]*n
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        res.append(sum(used))
    print(min(res))

Submission status: Runtime Error

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

import sys

sys.setrecursionlimit(2000)

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
if k%2 == 0:
    for i in range(n):
        temp = search(-1, i, k//2)
        if temp > ret:
            ret = temp
else:           
    for i in range(n):
        temp = first_search(i, k)
        if temp > ret:
            ret = temp
        
print(n-ret)

Submission status: Runtime Error

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

import sys

sys.setrecursionlimit(2000)

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
        

print(n-ret)

Submission status: Runtime Error

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

import sys

sys.setrecursionlimit(2000)

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: Runtime Error

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


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)

l2 = [0 for i in range(n)]

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: Runtime Error

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 = [[(1,i+1)] for i in range(1999)]
adj_list.append([])
edges = []
for i in range(1,2000):
	adj_list[i].append((1,i-1))
	edges.append((i-1,i))
    
for i in range(2000):
	d = bfs(adj_list, i)

start = t.clock()

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: Runtime Error

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)

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

# 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: Runtime Error

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)

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: Runtime Error

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)

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

withinK = np.count_nonzero(ie, axis=0)
# for i in range(N):
#     withinK[i] = np.count_nonzero(ie[i])
# print("withinK=", withinK)
maxBall = np.amax(withinK)
# print("maxBall=", maxBall)
solution = N - maxBall
print(solution)

Submission status: Runtime Error

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

Submission status: Runtime Error

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:
        dist = [min(d1, d2) for d1, d2 in zip(dist[a], dist[b])]
        ans = min(ans, len(list(filter(lambda x: (K-1) / 2 < x, dist))))

print(ans)

Submission status: Runtime Error

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