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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
tree = [[] for _ in range(N)]
edges = []
for n in range(1, N):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)
    edges.append((a - 1, b - 1))


def dfs(i, now_v):
    dias[i] = now_v
    for next_node in tree[i]:
        if dias[next_node] == -1:
            dfs(next_node, now_v + 1)


ans = int(1e18)
if K % 2 == 0:
    for i in range(N):
        dias = [-1 for _ in range(N)]
        dfs(i, 0)
        over_count = sum([1 if dias[j] > K / 2 else 0 for j in range(N)])
        ans = min(ans, over_count)
    print(ans)
else:
    for edge in edges:
        a, b = edge
        dias = [-1 for _ in range(N)]
        dfs(a, 0)
        temp_dias = list(dias)
        dias = [-1 for _ in range(N)]
        dfs(b, 0)
        # dists = [min(x, y) for x, y in zip(temp_dias, dias)]
        # print(i, j, dists)
        # x = sum([1 if dists[j] > (K - 1) / 2 else 0 for j in range(N)])
        x = sum(int(min(x, y) > (K - 1) / 2) for x, y in zip(temp_dias, dias))
        # print(x)
        ans = min(ans, x)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
tree = [[] for _ in range(N)]
edges = []
for n in range(1, N):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)
    edges.append((a - 1, b - 1))


def dfs(i, now_v):
    dias[i] = now_v
    for next_node in tree[i]:
        if dias[next_node] == -1:
            dfs(next_node, now_v + 1)

ans = int(1e18)
if K % 2 == 0:
    for i in range(N):
        dias = [-1 for _ in range(N)]
        dfs(i, 0)
        # print(dias)
        x = sum([1 if dias[j] > K / 2 else 0 for j in range(N)])
        # print(x)
        ans = min(ans, x)
    print(ans)
else:
    for edge in edges:
        i, j = edge
        dias = [-1 for _ in range(N)]
        dfs(i, 0)
        temp_dias = list(dias)
        dias = [-1 for _ in range(N)]
        dfs(j, 0)
        dists = [min(x, y) for x, y in zip(temp_dias, dias)]
        # print(i, j, dists)
        x = sum([1 if dists[j] > (K - 1) / 2 else 0 for j in range(N)])
        # print(x)
        ans = min(ans, x)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
tree = [[0 for n in range(N)] for _ in range(N)]
edges = []
for n in range(1, N):
    a, b = map(int, input().split())
    tree[a - 1][b - 1] = 1
    tree[b - 1][a - 1] = 1
    edges.append((a - 1, b - 1))

dias = [-1 for _ in range(N)]


def dfs(i, now_v):
    dias[i] = now_v
    for n in range(N):
        if dias[n] == -1 and tree[i][n] == 1:
            dfs(n, now_v + 1)

ans = int(1e18)
if K % 2 == 0:
    for i in range(N):
        dias = [-1 for _ in range(N)]
        dfs(i, 0)
        # print(dias)
        x = sum([1 if dias[j] > K / 2 else 0 for j in range(N)])
        # print(x)
        ans = min(ans, x)
    print(ans)
else:
    for edge in edges:
        i, j = edge
        if tree[i][j] == 1:
            dias = [-1 for _ in range(N)]
            dfs(i, 0)
            temp_dias = list(dias)
            dias = [-1 for _ in range(N)]
            dfs(j, 0)
            dists = [min(x, y) for x, y in zip(temp_dias, dias)]
            # print(i, j, dists)
            x = sum([1 if dists[j] > (K - 1) / 2 else 0 for j in range(N)])
            # print(x)
            ans = min(ans, x)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
tree = [[0 for n in range(N)] for _ in range(N)]
disj = [0 for n in range(N)]
for n in range(1, N):
    a, b = map(int, input().split())
    tree[a - 1][b - 1] = 1
    tree[b - 1][a - 1] = 1
    disj[a - 1] += 1
    disj[b - 1] += 1

dias = [-1 for _ in range(N)]


def dfs(i, now_v):
    dias[i] = now_v
    for n in range(N):
        if dias[n] == -1 and tree[i][n] == 1:
            dfs(n, now_v + 1)

"""
dfs(0, 0)
max_node = dias.index(max(dias))
dias = [-1 for _ in range(N)]
dfs(max_node, 0)
print(dias)
D = max(dias)
"""

ans = int(1e18)
if K % 2 == 0:
    for i in range(N):
        dias = [-1 for _ in range(N)]
        dfs(i, 0)
        # print(dias)
        x = sum([1 if dias[j] > K / 2 else 0 for j in range(N)])
        # print(x)
        ans = min(ans, x)
    print(ans)
else:
    for i in range(N):
        for j in range(i, N):
            if tree[i][j] == 1:
                dias = [-1 for _ in range(N)]
                dfs(i, 0)
                temp_dias = list(dias)
                dias = [-1 for _ in range(N)]
                dfs(j, 0)
                dists = [min(x, y) for x, y in zip(temp_dias, dias)]
                # print(i, j, dists)
                x = sum([1 if dists[j] > (K - 1) / 2 else 0 for j in range(N)])
                # print(x)
                ans = min(ans, x)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, raw_input().split())
    a = []
    g = [[] for _ in xrange(n)]
    for _ in xrange(n - 1):
        u, v = map(int, raw_input().split())
        u -= 1
        v -= 1
        a.append((u, v))
        g[u].append(v)
        g[v].append(u)
    st = []
    pu = st.append
    po = st.pop
    ans = 0
    if k % 2:
        k = k / 2 + 1
        for u, v in a:
            c = 0
            pu((u, k, v))
            pu((v, k, u))
            while st:
                u, d, p = po()
                d -= 1
                c += 1
                if d:
                    for v in g[u]:
                        if v != p:
                            pu((v, d, u))
            if ans < c:
                ans = c
    else:
        k = k / 2 + 1
        for i in xrange(n):
            c = 0
            pu((i, k, -1))
            while c < len(st):
                u, d, p = st[c]
                d -= 1
                if d:
                    for v in g[u]:
                        if v != p:
                            pu((v, d, u))
                c += 1
            if ans < c:
                ans = c
            del st[:]
    print n - ans
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, raw_input().split())
    a = []
    g = [[] for _ in xrange(n)]
    for _ in xrange(n - 1):
        u, v = map(int, raw_input().split())
        u -= 1
        v -= 1
        a.append((u, v))
        g[u].append(v)
        g[v].append(u)
    st = []
    pu = st.append
    po = st.pop
    ans = 0
    if k % 2:
        k = k / 2 + 1
        for u, v in a:
            c = 0
            pu((u, k, v))
            pu((v, k, u))
            while st:
                u, d, p = po()
                d -= 1
                c += 1
                if d:
                    for v in g[u]:
                        if v != p:
                            pu((v, d, u))
            if ans < c:
                ans = c
    else:
        k = k / 2 + 1
        for i in xrange(n):
            c = 0
            pu((i, k, -1))
            while st:
                u, d, p = po()
                d -= 1
                c += 1
                if d:
                    for v in g[u]:
                        if v != p:
                            pu((v, d, u))
            if ans < c:
                ans = c
    print n - ans
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from pandas import DataFrame

n = raw_input()
a = [int(i) for i in n.split()]
list1 = []
sum = 0
arr = np.zeros([a[0]-1,3])
print arr
for i in range(int(a[0]-1)):
    x = raw_input()
    list1.append(x)

print list1

Submission status: Accepted

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+1, mm+1))
    v2 = sum(len(dist2[u]) for u in range(k+1, mm+1))
    if v1<v2:
        done.add(v)
    else:
        done.add(u)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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())
G = [[] for _ in range(N + 1)]
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)

def dfs_order(G, root=1):
    parent = [0] * (N + 1)
    order = []
    stack = [root]
    while stack:
        x = stack.pop()
        order.append(x)
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)
    return parent, order

parent, order = dfs_order(G)

dp1 = np.zeros((N + 1, N + 1), np.int32)
for v in order[::-1]:
    p = parent[v]
    dp1[v, 0] += 1
    dp1[p, 1:] += dp1[v, :-1]

dp2 = np.zeros((N + 1, N + 1), np.int32)
dp2[1] = dp1[1]
for v in order[1:]:
    p = parent[v]
    x = dp2[p].copy()
    x[1:] -= dp1[v, :-1]
    dp2[v, 1:] += x[:-1]
    dp2[v] += dp1[v]

dp3 = np.zeros((N + 1, N + 1), np.int32)
for v in order[1:]:
    p = parent[v]
    dp3[v] = dp1[v]
    x = dp2[p].copy()
    x[1:] -= dp1[v][:-1]
    dp3[v] += x

# 距離 r まで生き残らせるとして、生き残る点の数
dp2.cumsum(axis=1, out=dp2)
dp3.cumsum(axis=1, out=dp3)

if K % 2 == 0:
    x = dp2[:, K // 2].max()
else:
    x = dp3[:, K // 2].max()

print(N - x)

Submission status: Accepted

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,-1] for _ in range(n+1)]
  dep[center] = [0,0]
  while stack:
    x = stack.pop()
    for i,y in enumerate(graph[x]):
      if x == center:
        dep[y] = [1,i+1]
        stack.append(y)
      else:
        if dep[y][0] == -1:
          stack.append(y)
          dep[y][0] = dep[x][0]+1
          dep[y][1] = dep[x][1]
  anstmp = 0
  bonus = [0]*(len(graph[center])+1)
  for i in range(1,n+1):
    if dep[i][0] <= rad:
      anstmp += 1
    if dep[i][0] == rad+1:
      bonus[dep[i][1]] += 1
  if k%2:
    anstmp += max(bonus)
  ans = min(n-anstmp,ans)
print(max(ans,0))

Submission status: Accepted

Solution code:
#参考コード
#https://atcoder.jp/contests/agc001/submissions/4594416
from collections import defaultdict,deque

N,K=map(int,input().split())
tree=[]
Graph=defaultdict(list)

for _ in range(N-1):
  edge=list(map(int,input().split()))
  Graph[edge[0]].append(edge[1])
  Graph[edge[1]].append(edge[0])
  tree.append(edge)
  
def DFSans(start,diam):
  visited=[0]*N
  q=deque()
  for s in start:
    q.append((s,0))
    visited[s-1]=1
  while q:
    search,start_diam=q.pop()
    if start_diam>=diam:
      continue
    for n in Graph[search]:
      if visited[n-1]:
        continue
      q.append((n,start_diam+1))
      visited[n-1]=1
    #print(q,visited)
  return N-sum(visited)

ans=99999999999999999999
if K%2==1:
  for i in range(N-1):
    ans=min(ans,DFSans(tree[i],(K-1)//2))
else:
  for i in range(1,N+1):
    ans=min(ans,DFSans([i],K//2))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def bfs(links, s, limit, bits):
    not_reachable = (1 << len(links)) - 1
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable ^= bits[v]
        cost += 1
        for u in links[v]:
            if u != p:
                q.append((cost, u, v))
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in ab:
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    limit = k // 2
    bits = [1 << i for i in range(n)]
    if k % 2 == 0:
        ans = min(bin(bfs(links, v, limit, bits)).count('1') for v in range(n))
    else:
        dists = [bfs(links, v, limit, bits) for v in range(n)]
        ans = min(bin(dists[a - 1] & dists[b - 1]).count('1') for a, b in ab)
    return ans


n, k = map(int, sys.stdin.buffer.readline().split())
ab = map(int, sys.stdin.buffer.read().split())
ab = list(zip(ab, ab))
print(solve(n, k, ab))

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
link = [[] for _ in range(n)]
ln = []
for i in range(n-1):
    a,b = list(map(int,input().split()))
    link[a-1].append(b-1)
    link[b-1].append(a-1)
    ln.append([a-1,b-1])

if k==1:
    print(n-2)
    exit()

from collections import deque
def get_v(node,dist):
    Q = deque()
    Q.append([node,0])
    visited=[-1]*n
    visited[node]=1
    while Q:
        now,cnt = Q.popleft()
        if cnt > dist:
            break
        for nxt in link[now]:
            if visited[nxt]!=-1:
                continue
            visited[nxt]=cnt+1
            Q.append([nxt,cnt+1])
    for i in range(n):
        if visited[i] == -1:
            ret = 0
        elif visited[i] <= dist:
            ret = 1
        else:
            ret = 0
        visited[i] = ret
    return visited
def borsm(l1,l2):
    sm=0
    for b1,b2 in zip(l1,l2):
        sm+=(b1 | b2)
    return sm
ans=float("inf")
if k%2==0:
    for i in range(n):
        ret = n - sum(get_v(i,k//2))
        ans=min(ret,ans)
else:
    for tmp in ln:
        n1,n2=tmp
        c1=get_v(n1,k//2)
        c2=get_v(n2,k//2)
        ret = n- borsm(c1,c2)
        ans=min(ret,ans)
print(ans)

Submission status: Accepted

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 p in range(n):
                if d[p] > k // 2:
                    c += 1
            ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
# tree diameter if (currDia <= k) true else shorten() while (dia >= k) O(n) dia readjust 
# multiple pairs . centroid of tree --> on largest path find centroid --> maintain a heap ?

from collections import deque

def main():

    n, d = map(int, input().split())

    adj = [[] for i in range(n)]

    edges = []

    for i in range(n-1):

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

        adj[a-1].append(b-1)

        adj[b-1].append(a-1)

        edges.append((a-1, b-1))


    ans = 1000000

    if (d % 2 == 0):
        for i in range(n):
            ans = min(ans, compute(adj, i, d))
    else:
        for i in range(n-1):
            ans = min(ans, computeEdges(adj, edges[i], d-1))

    print(ans)

def compute(adj, u, dia):

    vis = [False]*len(adj)

    dis = [0]*len(adj)

    q = deque()

    q.append(u)
    vis[u] = True

    while (len(q) > 0):

        elem = q.popleft()

        for v in adj[elem]:

            if (vis[v] == False):
                q.append(v)

                vis[v] = True

                dis[v] = dis[elem] + 1

    count = 0

    for a in dis:

        if (a > dia/2):
            count += 1

    return count


def computeEdges(adj, edge, dia):

    vis = [False]*len(adj)

    dis = [0]*len(adj)

    q = deque()

    q.append(edge[0])
    q.append(edge[1])
    vis[edge[0]] = True
    vis[edge[1]] = True

    while (len(q) > 0):

        elem = q.popleft()

        for v in adj[elem]:

            if (vis[v] == False):
                q.append(v)

                vis[v] = True

                dis[v] = dis[elem] + 1

    count = 0

    for a in dis:

        if (a > dia/2):
            count += 1

    return count

main()

Submission status: Accepted

Solution code:

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

今度こそ通すぞ！！
制約が小さいので、各頂点に関して最短距離探索するぐらいはできる

直径の中央で全探索する？
→距離K//2以内の頂点の数を数え、残りを取り除けばよい
→その点を通らない長さK以上のパスは存在しえない

Kが偶数なら、1点を中心(深さ0)とし探索
Kが奇数なら、隣接する2点を深さ0とすればよい

計算量はO(N**2)

"""
from collections import deque
N,K = map(int,input().split())

AB = []

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)

    AB.append([A,B])

ans = float("inf")

if K % 2 == 0: #偶数の場合

    for st in range(N):
        q = deque([st])
        dis = [float("inf")] * N
        dis[st] = 0
        nps = 0

        while len(q) > 0:

            now = q.popleft()
            nps += 1

            if dis[now] < K//2:

                for nex in lis[now]:
                    if dis[nex] > dis[now] + 1:
                        dis[nex] = dis[now] + 1
                        q.append(nex)
                        
        ans = min(ans , N - nps)

else:

    for i in range(N-1):
        a,b = AB[i]
        q = deque([a,b])
        dis = [float("inf")] * N
        dis[a] = 0
        dis[b] = 0
        nps = 0

        while len(q) > 0:

            now = q.popleft()
            nps += 1

            if dis[now] < K//2:

                for nex in lis[now]:
                    if dis[nex] > dis[now] + 1:
                        dis[nex] = dis[now] + 1
                        q.append(nex)
                        
        ans = min(ans , N - nps)   

print (ans)

Submission status: Accepted

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)]
uv = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
    uv.append((a, b))

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 
if k % 2 == 0:
    for i in range(n):
        ret = dfs(-1, i, 0)
        ans = min(ans, ret)
else:
    for u, v in uv:
        ret = dfs(u, v, 0) + dfs(v, u, 0)
        ans = min(ans, ret)

print(ans)

Submission status: Accepted

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(q)
                for step in range(N-1):
                    if step*2 > (K-1):
                        res += len(q)
                    tmp = []
                    while q:
                        v = q.pop()
                        visited.add(v)
                        for u in edge[v]:
                            if u in visited:
                                continue
                            visited.add(u)
                            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: Accepted

Solution code:
from collections import deque

N, K, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

def solve(a, b):
    D = [-1] * (N + 1)

    if a == b:
        Q = deque([a])
        r = K // 2
        D[a] = 0
    else:
        Q = deque([a, b])
        r = (K - 1) // 2
        D[a] = D[b] = 0

    cnt = len(Q)
    while Q:
        v = Q.popleft()

        d = D[v] + 1
        if d > r:
            break

        for u in E[v]:
            if D[u] == -1:
                cnt += 1
                D[u] = d
                Q.append(u)

    return N - cnt


if K % 2 == 1:
    print(min(solve(a, b) for a, b in zip(*[iter(AB)] * 2)))
else:
    print(min(solve(a, a) for a in range(1, N + 1)))

Submission status: Accepted

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

from collections import deque

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点
        q = deque([a])
        r = K // 2
    else:
        # 中心が辺
        q = deque([a,b])
        r = (K-1)//2
    dist = [INF] * (N+1)
    for x in q:
        dist[x] = 0
    pop = q.popleft; append = q.append
    cnt = len(q)
    while q:
        v = pop()
        dw = dist[v] + 1
        if dw > r:
            break
        for w in graph[v]:
            if dist[w] == INF:
                cnt += 1
                dist[w] = dw
                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: Accepted

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=0
        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 L[Q[q][0]]:
                        if C[k]==10000:
                            Q.append([k,Q[q][1]+1])
        if N-cnt<ans:
            ans=N-cnt
        #print(i,C)
    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))

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


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

cnt = [0]
def search(cur, prev, depth, k):
    if depth > k:
        cnt[0] += 1
    for to in G[cur]:
        if to != prev:
            search(to, cur, depth+1, k)


ans = float("inf")
# 点中心
if k % 2 == 0:
    for i in range(n):
        cnt = [0]
        search(i, -1, 0, k//2)
        ans = min(ans, cnt[0])
# 辺中心
else:
    for a, b in edges:
        cnt = [0]
        search(a, b, 0, k//2)
        search(b, a, 0, k//2)
        ans = min(ans, cnt[0])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, k = map(int, input().split())
graph = [[] for _ in range(n+1)]
ab_list = []
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    ab_list.append((a, b))

ans = 2000
max_distance = k // 2

if k % 2 == 0:
    for i in range(1, n+1):
        extra_node_cnt = 0
        q = deque()
        q.append((i, 0))
        seen = [0]*(n+1)
        seen[i] = 1
        while q:
            node, distance = q.popleft()
            if distance > max_distance:
                extra_node_cnt += 1
            for neighor_node in graph[node]:
                if seen[neighor_node] == 0:
                    seen[neighor_node] = 1
                    q.append((neighor_node, distance + 1))
        ans = min(ans, extra_node_cnt)
else:
    for now_node, now_neighbor in ab_list:
        extra_node_cnt = 0
        q = deque()
        q.append((now_node, 0))
        seen = [0]*(n+1)
        seen[now_node] = 1
        seen[now_neighbor] = 1
        while q:
            node, distance = q.popleft()
            if distance > max_distance:
                extra_node_cnt += 1
            for neighor_node in graph[node]:
                if seen[neighor_node] == 0:
                    seen[neighor_node] = 1
                    q.append((neighor_node, distance + 1))
        q = deque()
        q.append((now_neighbor, 0))
        seen = [0]*(n+1)
        seen[now_node] = 1
        seen[now_neighbor] = 1
        while q:
            node, distance = q.popleft()
            if distance > max_distance:
                extra_node_cnt += 1
            for neighor_node in graph[node]:
                if seen[neighor_node] == 0:
                    seen[neighor_node] = 1
                    q.append((neighor_node, distance + 1))
        ans = min(ans, extra_node_cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,K = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]

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

def count_nbd(x,R,parent):
    # parentを含まない部分木
    # xを含む、xから半径R内の点の個数を数える
    count = 0
    visited = [False] * (N+1)
    visited[x] = True
    visited[parent] = True
    count += 1
    q = [x]
    for _ in range(R):
        qq = []
        for y in q:
            for z in graph[y]:
                if visited[z]:
                    continue
                visited[z] = True
                qq.append(z)
                count += 1
        q = qq
    return count

if K&1:
    # 辺の中点に中心がある場合
    R = (K-1)//2
    x = max(count_nbd(x,R,y) + count_nbd(y,R,x) for x,y in AB)
else:
    # 頂点が中心
    R = K//2
    x = max(count_nbd(x,R,0) for x in range(1,N+1))

answer = N-x
print(answer)