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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,k = map(int, input().split())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    dist = defaultdict(list)
    dist[0].append(start)
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None and v not in done:
                seen[v] = d + 1
                dist[d+1].append(v)
                q.appendleft(v)
    return seen, dist
ans = 0
done = set()
while True:
    start = 0
    while start in done:
        start += 1
    seen, dist1 = bfs(start)
    m = max(item for item in seen if item is not None)
    u = dist1[m][0]
    seen, dist1 = bfs(u)
    mm = max(item for item in seen if item is not None)
    if mm<=k:
        break
    ans += 1
    v = dist1[mm][0]
    seen, dist2 = bfs(v)
    v1 = sum(len(dist1[u]) for u in range(k, mm+1))
    v2 = sum(len(dist2[u]) for u in range(k, mm+1))
    if v1<v2:
        done.add(v)
    else:
        done.add(u)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,k = map(int, input().split())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    dist = defaultdict(list)
    dist[0].append(start)
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None and v not in done:
                seen[v] = d + 1
                dist[d+1].append(v)
                q.appendleft(v)
    return seen, dist
ans = 0
done = set()
while True:
    start = 0
    while start in done:
        start += 1
    seen, dist1 = bfs(start)
    m = max(item for item in seen if item is not None)
    u = dist1[m][0]
    seen, dist1 = bfs(u)
    mm = max(item for item in seen if item is not None)
    if mm<=k:
        break
    ans += 1
    v = dist1[mm][0]
    seen, dist2 = bfs(v)
    val = mm
    while val>=0 and len(dist1[val])==len(dist2[val]):
        val -= 1
    if len(dist1[val])<len(dist2[val]):
        done.add(v)
    else:
        done.add(u)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,k = map(int, input().split())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    dist = defaultdict(list)
    dist[0].append(start)
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None and v not in done:
                seen[v] = d + 1
                dist[d+1].append(v)
                q.appendleft(v)
    return seen, dist
ans = 0
done = set()
while True:
    start = 0
    while start in done:
        start += 1
    seen, dist1 = bfs(start)
    m = max(item for item in seen if item is not None)
    u = dist1[m][0]
    seen, dist1 = bfs(u)
    mm = max(item for item in seen if item is not None)
    if mm<=k:
        break
    ans += 1
    v = dist1[mm][0]
    seen, dist2 = bfs(v)
    if len(dist1[mm])<len(dist2[mm]):
        done.add(v)
    else:
        done.add(u)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,k = map(int, input().split())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    dist = defaultdict(list)
    dist[0].append(start)
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None and v not in done:
                seen[v] = d + 1
                dist[d+1].append(v)
                q.appendleft(v)
    return seen, dist
ans = 0
done = set()
while True:
    start = 0
    while start in done:
        start += 1
    seen, dist = bfs(start)
    m = max(item for item in seen if item is not None)
    u = dist[m][0]
    seen, dist = bfs(u)
    mm = max(item for item in seen if item is not None)
    if mm<=k:
        break
    ans += 1
    if len(dist[mm])==1:
        v = dist[mm][0]
        done.add(v)
    else:
        done.add(u)
print(ans)

Submission status: Wrong Answer

Solution code:
 
class tree_unit:
  def __init__(self, name):
    self.name = name
    self.conn = []
  def add_conn(self, vectex):
    self.conn.append(vectex)
  def search(self, vectex):
    if vectex in self.conn:
      conn = self.conn[:].remove(vectex)
      return conn
    else:
      return []
  def __repr__(self):
    return str(self.name)

N, K = [int(x) for x in input().split()]

units = [tree_unit(0)]
for vec in range(1, N+1):
  units.append(tree_unit(vec))
  
for i in range(N-1):
  A, B = [int(x) for x in input().split()]
  units[A].add_conn(B)
  units[B].add_conn(A)

start = 1
for i in range(1, N+1):
  if len(units[i].conn) == 1:
    start = i

cur = units[start].conn[0]
stack = [cur]
visited = [False for i in range(N+1)]
depth = [0 for i in range(N+1)]
depth[start] = 1
depth[cur] = 2
depth_var = 3
visited[start] = True
while stack:
  cur = stack.pop()
  visited[cur] = True
  exist = False
  for vec in units[cur].conn:
    if not visited[vec]:
      stack.append(vec)
      depth[vec] = depth_var
      exist = True
  if exist:
    depth_var += 1

max_depth = max(depth)
if max_depth <= K:
  print(0)
else:
  dif = max_depth - K
  count_up, count_down = 0, 0
  for v in depth[1:]:
    if v > max_depth-dif:
      count_up += 1
    elif v <= dif:
      count_down += 1
  print(min(count_up, count_down))

Submission status: Wrong Answer

Solution code:
 
class tree_unit:
  def __init__(self, name):
    self.name = name
    self.conn = []
  def add_conn(self, vectex):
    self.conn.append(vectex)
  def search(self, vectex):
    if vectex in self.conn:
      conn = self.conn[:].remove(vectex)
      return conn
    else:
      return []
  def __repr__(self):
    return str(self.name)

N, K = [int(x) for x in input().split()]

units = [[tree_unit(0), 0, False]]
for vec in range(1, N+1):
  units.append([tree_unit(vec), 0, False])
  
for i in range(N-1):
  A, B = [int(x) for x in input().split()]
  units[A][0].add_conn(B)
  units[B][0].add_conn(A)

ones = []
for i in range(1, N+1):
  units[i][1] = len(units[i][0].conn)
  if units[i][1] == 1:
    ones.append(i)

start = ones[0]
cur = units[start][0].conn[0]
stack = [cur]
depth = [0 for i in range(N+1)]
depth[start] = 1
depth[cur] = 2
depth_var = 3
units[start][2] = True
while stack:
  cur = stack.pop()
  units[cur][2] = True
  exist = False
  for vec in units[cur][0].conn:
    if not units[vec][2]:
      stack.append(vec)
      depth[vec] = depth_var
      exist = True
  if exist:
    depth_var += 1

max_depth = max(depth)
if max_depth <= K:
  print(0)
else:
  dif = max_depth - K
  count_up, count_down = 0, 0
  for v in depth[1:]:
    if v > max_depth-dif:
      count_up += 1
    elif v <= dif:
      count_down += 1
  print(min(count_up, count_down))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
ans = n
rad = k//2
for center in range(1,n+1):
  stack = [center]
  dep = [-1]*(n+1)
  dep[center] = 0
  while stack:
    x = stack.pop()
    for y in graph[x]:
      if dep[y] == -1:
        stack.append(y)
        dep[y] = dep[x]+1
  anstmp = 0
  for i in range(1,n+1):
    if dep[i] <= rad:
      anstmp += 1
  if k%2:
    anstmp += 1
  ans = min(n-anstmp,ans)
print(max(ans,0))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
g = [[] for _ 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)
if k % 2 == 0:
    ans = 100000
    for i in range(n):
        s = [i]
        d = [-1] * n
        d[i] = 0
        while s:
            p = s.pop()
            for node in g[p]:
                if d[node] == -1:
                    s.append(node)
                    d[node] = d[p] + 1
        c = 0
        for i in range(n):
            if d[i] > k // 2:
                c += 1
        ans = min(ans, c)
else:
    ans = 100000
    for i in range(n):
        for j in g[i]:
            s = [i, j]
            d = [-1] * n
            d[i] = 0
            d[j] = 0
            while s:
                p = s.pop()
                for node in g[p]:
                    if d[node] == -1:
                        s.append(node)
                        d[node] = d[p] + 1
            c = 0
            for i in range(n):
                if d[i] > k // 2:
                    c += 1
            ans = min(ans, c)
print(ans)

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc001/tasks/agc001_c

削除後のグラフが連結だから、葉の方から消していく必要がある

直径の一端となる頂点と、そこから伸びている辺を全探索？
距離がK以下の頂点の数の最大値が答え
1辺が高々2回選択されるので O(N**2)

"""
import sys
sys.setrecursionlimit(10 ** 5)

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

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

ans = float("inf")

def dfs(v,np,dep):

    ret = 1
    if dep == K:
        return ret
    
    for nex in lis[v]:
        if nex != np:
            ret += dfs(nex,v,dep+1)
    return ret

for st in range(N):

    for fp in lis[st]:

        now = 1 + dfs(st,fp,1)
        ans = min(ans , N-now)

print (ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


n, k = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

def solve(root):
    visited = [-1] * n
    visited[root] = 0
    res = 0
    for v in tree[root]:
        q = deque([v])
        visited[v] = 1
        cnt = 2
        while q:
            v = q.pop()
            if visited[v] >= k:
                continue
            for nxt_v in tree[v]:
                if visited[nxt_v] != -1:
                    continue
                visited[nxt_v] = visited[v] + 1
                cnt+= 1
                q.append(nxt_v)
        res = max(cnt, res)
    return res

ans = 0
for i in range(n):
    ans = max(solve(i), ans)
print(n - ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

n, k = map(int, input().split())
radius = k // 2
edge = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

def dfs(p, v, d):
    ret = 0
    for nv in edge[v]:
        if nv == p:
            continue
        ret += dfs(v, nv, d+1)
    if d > radius:
        return ret + 1
    else:
        return ret

ans = n 
for i in range(n):
    ret = dfs(-1, i, 0)
    ans = min(ans, ret)

if k % 2 == 1:
    ans = max(0, ans-1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]

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

insides = 0
if k%2==0:     
    #各頂点始まり、で調べる
    for i in range(n):
        queue = deque([i])
        dist = [-1]*n
        dist[i] = 0
        
        #幅優先探索
        while queue:
            u = queue.popleft()
            d = dist[u]
            #幅優先探索ゆえ、k/2になったら終えてしまえばよい。
            if d==k//2:
                continue

            nodes = edges[u]
            for v in nodes:
                if dist[v]==-1: #未踏.
                    dist[v] = d + 1
                    queue.append(v)

        cnt = 0
        for v in dist:
            if v != -1:
                cnt += 1
        insides = max(cnt, insides)
        
else:
    #各枝始まり、で調べる
    for i,e in enumerate(edges):
        for v in e:
            queue = deque([i,v])
            dist = [-1]*n
            dist[i] = 0
            dist[v] = 0

        #幅優先探索
        while queue:
            u = queue.popleft()
            d = dist[u]
            #幅優先探索ゆえ、k/2になったら終えてしまえばよい。
            if d==k//2:
                continue

            nodes = edges[u]
            for v in nodes:
                if dist[v]==-1: #未踏.
                    dist[v] = d + 1
                    queue.append(v)

        cnt = 0
        for v in dist:
            if v != -1:
                cnt += 1
        insides = max(cnt, insides)
        
    

print(n-insides)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]

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

insides = 0
if k%2==0:     
    #各頂点始まり、で調べる
    for i in range(n):
        queue = deque([i])
        dist = [-1]*n
        dist[i] = 0
        
        #幅優先探索
        while queue:
            u = queue.popleft()
            d = dist[u]
            #幅優先探索ゆえ、k/2になったら終えてしまえばよい。
            if d==k//2:
                break

            nodes = edges[u]
            for v in nodes:
                if dist[v]==-1: #未踏.
                    dist[v] = d + 1
                    queue.append(v)

        cnt = 0
        for v in dist:
            if v != -1:
                cnt += 1
        insides = max(cnt, insides)
        
else:
    #各枝始まり、で調べる
    for i,e in enumerate(edges):
        for v in e:
            queue = deque([i,v])
            dist = [-1]*n
            dist[i] = 0
            dist[v] = 0

        #幅優先探索
        while queue:
            u = queue.popleft()
            d = dist[u]
            #幅優先探索ゆえ、k/2になったら終えてしまえばよい。
            if d==k//2:
                break

            nodes = edges[u]
            for v in nodes:
                if dist[v]==-1: #未踏.
                    dist[v] = d + 1
                    queue.append(v)

        cnt = 0
        for v in dist:
            if v != -1:
                cnt += 1
        insides = max(cnt, insides)
        
    

print(n-insides)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    edge = [[]for _ in range(N)]
    for _ in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    ans = inf
    if K&1: #辺が中心となり、両端点からどのへんにもD/2イカ
        for a,l in enumerate(edge):
            for b in l:
                res = 0
                q = [a,b]
                visited = set()
                for step in range(N-1):
                    if step*2 > (K-1):
                        res += len(q)
                    tmp = []
                    while q:
                        v = q.pop()
                        if v in visited:
                            continue
                        visited.add(v)
                        for u in edge[v]:
                            if u in visited:
                                continue
                            tmp.append(u)
                    q = tmp

                ans = min(res, ans)

    else: #点が中心となり、どのへんにもD/2イカ
        for center in range(N):
            res = 0
            q = [center]
            visited = set()
            for step in range(N-1):
                tmp = []
                if step*2 > K:
                    res += len(q)
                while q:
                    v = q.pop()
                    if v in visited:
                        continue
                    visited.add(v)
                    for u in edge[v]:
                        if u in visited:
                            continue
                        tmp.append(u)
                q = tmp
            ans = min(res, ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    edge = [[]for _ in range(N)]
    for _ in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    ans = inf
    if K&1: #辺が中心となり、両端点からどのへんにもD/2イカ
        for a,l in enumerate(edge):
            for b in l:
                res = 0
                q = [a,b]
                visited = set()
                for step in range(N-1):
                    tmp = []
                    while q:
                        v = q.pop()
                        if v in visited:
                            continue
                        visited.add(v)
                        for u in edge[v]:
                            if u in visited:
                                continue
                            tmp.append(u)
                    q = tmp
                    if step*2 > (K-1):
                        res += len(q)

                ans = min(res, ans)

    else: #点が中心となり、どのへんにもD/2イカ
        for center in range(N):
            res = 0
            q = [center]
            visited = set()
            for step in range(N-1):
                tmp = []
                if step*2 > K:
                    res += len(q)
                while q:
                    v = q.pop()
                    if v in visited:
                        continue
                    visited.add(v)
                    for u in edge[v]:
                        if u in visited:
                            continue
                        tmp.append(u)
                q = tmp
            ans = min(res, ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from bisect import insort_left

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

def MAXDIST(s):
    dist = [None] * N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + 1
            que.append(w)
    d = 0
    for x in dist:
        if x is not None:
            d = max(d, x)
    return dist.index(d)

def cut_tree(s):
    dist = [None] * N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        if d == K:
            break
        for w in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + 1
            que.append(w)
    cut_list = tuple(i for i in range(N) if dist[i] is None)
    return cut_list

def main():
    ans = 0
    tmp = G
    while True:
        for i,x in enumerate(G):
            if x:
                sta = i
        u = MAXDIST(sta)
        cut_list = cut_tree(u)
        ans += len(cut_list)
        if not cut_list:
            break
        for i in range(N):
            for E in cut_list:
                if i == E:
                    G[i] = []
                    continue
                try:
                    G[i].remove(E)
                except ValueError as e:
                    pass
        if tmp == G:
            break
        else:
            tmp = G
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

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

def MAXDIST(s):
    dist = [None] * N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + 1
            que.append(w)
    d = max(dist)
    return dist.index(d), d

def cut_cnt(s):
    dist = [None] * N
    que = deque([s])
    dist[s] = 0
    cnt  = 1
    while que:
        v = que.popleft()
        d = dist[v]
        if d == K:
            break
        for w in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + 1
            que.append(w)
            cnt += 1
    return N - cnt

def main():
    # u: 頂点0との最長頂点間距離
    u, _ = MAXDIST(0)
    print(cut_cnt(u))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

ans = 10 ** 9

for i in range(1, N + 1):
    if len(edge[i]) > 1:
        continue

    cnt = 0  # 削除すべき節点
    depth = [-1] * (N + 1)
    depth[i] = 0
    node = deque([i])

    while node:
        s = node.popleft()
        d = depth[s]
        if d > K:
            cnt += 1
        for t in edge[s]:
            if depth[t] != -1:
                continue
            depth[t] = d + 1
            node.append(t)
    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

ans = 10 ** 9

for i in range(1, N + 1):
    if len(edge[i]) > 1:
        continue

    cnt = 0  # 削除すべき節点
    depth = [-1] * (N + 1)
    depth[i] = 0
    node = deque([i])

    while node:
        s = node.popleft()
        d = depth[s]
        for t in edge[s]:
            if depth[t] != -1:
                continue
            if d >= K:
                cnt += 1
            depth[t] = d + 1
            node.append(t)
    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
s = [0]
d = [-1] * n
d[0] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            s.append(node)
m = max(d)
ans = n
for i in range(n):
    if d[i] != m:
        continue
    s = [i]
    d1 = [-1] * n
    d1[i] = 0
    while s:
        p = s.pop()
        for node in g[p]:
            if d1[node] == -1:
                d1[node] = d1[p] + 1
                s.append(node)
    d1.sort(reverse=True)
    for j in range(n):
        if d1[j] <= k:
            break
    ans = min(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K = map(int,readline().split())
m = map(int,read().split())
AB = list(zip(m,m))

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

def F(a,b,K):
    INF = 10 ** 9
    if a == b:
        # 中心が1点
        stack = [a]
        r = K // 2
    else:
        # 中心が辺
        stack = [a,b]
        r = (K-1)//2
    dist = [INF] * (N+1)
    for x in stack:
        dist[x] = 0
    pop = stack.pop; append = stack.append
    cnt = len(stack)
    while stack:
        v = pop()
        dw = dist[v] + 1
        if dw > r:
            break
        for w in graph[v]:
            if dist[w] == INF:
                cnt += 1
                dist[w] = dw
                stack.append(w)
    return N - cnt

x = min(F(a,b,K) for a,b in AB)
y = min(F(a,a,K) for a in range(1,N+1))
answer = min(x,y)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K = map(int,readline().split())
m = map(int,read().split())
AB = list(zip(m,m))

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

def F(a,b,K):
    INF = 10 ** 9
    if a == b:
        # 中心が1点
        stack = [a]
        r = K // 2
    else:
        # 中心が辺
        stack = [a,b]
        r = (K-1)//2
    dist = [INF] * (N+1)
    for x in stack:
        dist[x] = 0
    pop = stack.pop; append = stack.append
    cnt = len(stack)
    while stack:
        v = pop()
        dw = dist[v] + 1
        if dw > r:
            break
        for w in graph[v]:
            if dist[w] == INF:
                cnt += 1
                dist[w] = dw
                stack.append(w)
    return N - cnt

if K & 1:
    answer = min(F(a,b,K) for a,b in AB)
else:
    answer = min(F(a,a,K) for a in range(1,N+1))
print(answer)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
L=[[]for i in range(N+1)]
l=[]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    l.append([a,b])
ans=N
if K%2==0:
    for i in range(1,N+1):
        C=[10000 for i in range(N+1)]
        Q=[[i,0]]
        cnt=1
        for q in range(10000):
            if q==len(Q):
                break
            if C[Q[q][0]]==10000:
                C[Q[q][0]]=Q[q][1]
                cnt+=1
                if Q[q][1]<K//2:
                    for k in range(len(L[Q[q][0]])):
                        if C[k]==10000:
                            Q.append([k,Q[q][1]+1])
        if N-cnt<ans:
            ans=N-cnt
    print(max(0,ans))
else:
    if K==1:
        print(N-2)
        exit()
    for a,b in l:
        C1=[10000 for i in range(N+1)]
        C2=[10000 for i in range(N+1)]
        X=[[a,0]]
        for q in range(10000):
            if q==len(X):
                break
            if C1[X[q][0]]==10000:
                C1[X[q][0]]=X[q][1]
                if X[q][1]<(K-1)//2:
                    for k in L[X[q][0]]:
                        if C1[k]==10000:
                            X.append([k,X[q][1]+1])
        Y=[[b,0]]
        for q in range(10000):
            if q==len(Y):
                break
            if C2[Y[q][0]]==10000:
                C2[Y[q][0]]=Y[q][1]
                if Y[q][1]<(K-1)//2:
                    for k in L[Y[q][0]]:
                        if C2[k]==10000:
                            Y.append([k,Y[q][1]+1])
        cnt=0
        for x in range(1,N+1):
            if C1[x]<=(K-1)//2 or C2[x]<=(K-1)//2:
                cnt+=1
        #print(a,b,cnt,C1,C2)
        if N-cnt<ans:
            ans=N-cnt
    print(max(0,ans))