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 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 < rad:
			cnt += rad_reach(h,nxt,dist+1,E,rad,ne)
		else:
			cnt += 1
	return cnt
def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [[] for i in xrange(N)]
	for i in xrange(N-1):
		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()

Submission status: Wrong Answer

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)
        over_count = sum([1 if dias[j] > K / 2 else 0 for j in range(N)])
        ans = min(ans, over_count)
    print(ans)
else:
    dias_lst = []
    for i in range(N):
        dias = [-1 for _ in range(N)]
        dfs(i, 0)
        dias_lst.append(list(dias))
    # print(dias_lst)
    for edge in edges:
        x = sum(int(min(x, y) > (K - 1) / 2)
                for x, y in zip(dias_lst[edge[0]], dias_lst[edge[1]]))
        ans = min(ans, x)
    print(ans)

Submission status: Wrong Answer

Solution code:
def main(le=len):
    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 c < le(st):
                u, d, p = po()
                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[:]
    else:
        k = k / 2 + 1
        for i in xrange(n):
            c = 0
            pu((i, k, -1))
            while c < le(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: Wrong Answer

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 get_start():
    for i in range(N):
        for j in range(N):
            if tree[i][j] == 1:
                return i


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)

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

ans = 0
max_dias = max(dias)
while True:
    # print(disj)
    if max_dias <= K:
        print(ans)
        exit()
    lst = [i for i in range(N) if disj[i] == 1]
    # print("lst", lst)
    counts = []
    for l in lst:
        count = 0
        for n in range(N):
            if tree[l][n] == 1:
                count = disj[n]
                break
        counts.append(count)
    # print("counts", counts)
    delete_node = lst[counts.index(min(counts))]
    # print("delete", delete_node)
    for i in range(N):
        if tree[i][delete_node] == 1:
            disj[i] -= 1
            tree[i][delete_node] = 0
            tree[delete_node][i] = 0
            if disj[i] == 1:
                max_dias -= 1
    disj[delete_node] = 0
    ans += 1
print(ans)

Submission status: Wrong Answer

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 get_start():
    for i in range(N):
        for j in range(N):
            if tree[i][j] == 1:
                return i


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)

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

ans = 0
while True:
    max_dias = max(dias)
    if max_dias <= K:
        print(ans)
        exit()
    lst = [i for i in range(N) if disj[i] == 1]
    counts = []
    for l in lst:
        count = 0
        for n in range(N):
            if tree[l][n] == 1:
                count += 1
        counts.append(count)
    delete_node = lst[counts.index(min(counts))]
    for i in range(N):
        tree[i][delete_node] = 0
        tree[delete_node][i] = 0
    disj[delete_node] = 0

    s = get_start()
    dfs(s, 0)
    max_node = dias.index(max(dias))
    dias = [-1 for _ in range(N)]
    dfs(max_node, 0)
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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
        q.extend((cost, u, v) for u in links[v] if u != p)
    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: Time Limit Exceeded

Solution code:
import sys
from collections import deque


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


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

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

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


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


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

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

    ans = n
    thr = k // 2
    if k % 2 == 0:
        ans = min(sum(bfs(links, v, thr)) for v in range(n))
    else:
        dists = [bfs(links, v, thr) for v in range(n)]
        for a, b in zip(ab[0::2], ab[1::2]):
            a -= 1
            b -= 1
            ans = min(ans, sum(d1 and d2 for d1, d2 in zip(dists[a], dists[b])))
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict


def bfs(links, s=0):
    ans = [0] * len(links)
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        ans[v] = cost
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return ans


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

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

    ans = n
    thr = k // 2
    if k % 2 == 0:
        for v in range(n):
            ans = min(ans, sum(d > thr for d in bfs(links, v)))
    else:
        cache = {}
        for a, b in zip(ab[0::2], ab[1::2]):
            a -= 1
            b -= 1
            if a in cache:
                da = cache[a]
            else:
                da = cache[a] = bfs(links, a)
            if b in cache:
                db = cache[b]
            else:
                db = cache[b] = bfs(links, b)
            ans = min(ans, sum(d1 > thr and d2 > thr for d1, d2 in zip(da, db)))
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, k, *ab = map(int, sys.stdin.buffer.read().split())
aaa = np.array(ab[0::2], dtype=np.int64) - 1
bbb = np.array(ab[1::2], dtype=np.int64) - 1
ccc = np.ones(n - 1, dtype=np.int64)
graph = csr_matrix((ccc, (aaa, bbb)), shape=(n, n))
dists = floyd_warshall(graph, directed=False)

if k % 2 == 0:
    print((dists > k // 2).sum(axis=0).min())
else:
    ans = n
    over = dists > k // 2
    for a, b in zip(ab[0::2], ab[1::2]):
        ans = min(ans, (over[a - 1] & over[b - 1]).sum())
    print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np
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=np.array(get_v(n1,k//2))
        c2=np.array(get_v(n2,k//2))
        ret = n- sum(c1 | c2)
        ans=min(ret,ans)

print(ans)

Submission status: Time Limit Exceeded

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 queue import Queue

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 = Queue(maxsize = len(adj))

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

    while (q.qsize() > 0):

        elem = q.get()

        for v in adj[elem]:

            if (vis[v] == False):
                q.put(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 = Queue(maxsize = len(adj))

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

    while (q.qsize() > 0):

        elem = q.get()

        for v in adj[elem]:

            if (vis[v] == False):
                q.put(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: Time Limit Exceeded

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 queue import Queue

def main():

    n, d = [int(x) for x in input().split(" ")]

    adj = []

    edges = []

    for i in range(n):
        adj.append([])

    for i in range(n-1):

        a, b = [int(x) for x in 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 = Queue(maxsize = len(adj))

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

    while (q.qsize() > 0):

        elem = q.get()

        for v in adj[elem]:

            if (vis[v] == False):
                q.put(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 = Queue(maxsize = len(adj))

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

    while (q.qsize() > 0):

        elem = q.get()

        for v in adj[elem]:

            if (vis[v] == False):
                q.put(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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  T = [[] for _ in range(n)]
  E = []
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))
  d = k//2
  def dfs(vs):
    dist = [-1]*n
    stack = []
    cnt = 0
    for v in vs:
      stack.append(v)
      dist[v] = 0
    while stack:
      v = stack.pop()
      for nv in T[v]:
        if dist[nv] == -1:
          t = dist[v] + 1
          dist[nv] = t
          if t > d:
            cnt += 1
          stack.append(nv)
    return cnt
  ans = n
  if k%2 == 0:
    for i in range(n):
      ans = min(ans, dfs([i]))
  else:
    for l in E:
      ans = min(ans, dfs(l))
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  T = [[] for _ in range(n)]
  E = []
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))
  d = k//2
  def dfs(vs):
    dist = [-1]*n
    stack = []
    cnt = 0
    for v in vs:
      stack.append(v)
      dist[v] = 0
    while stack:
      v = stack.pop()
      for nv in T[v]:
        if dist[nv] == -1:
          dist[nv] = dist[v] + 1
          if dist[nv] > d:
            cnt += 1
            if cnt >= ans:
              return cnt
          stack.append(nv)
    return cnt
  ans = n
  if k%2 == 0:
    for i in range(n):
      ans = min(ans, dfs([i]))
  else:
    for l in E:
      ans = min(ans, dfs(l))
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  T = [[] for _ in range(n)]
  E = []
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))
  d = k//2
  def dfs(vs):
    dist = [-1]*n
    stack = []
    cnt = 0
    for v in vs:
      stack.append(v)
      dist[v] = 0
    while stack:
      v = stack.pop()
      for nv in T[v]:
        if dist[nv] == -1:
          dist[nv] = dist[v] + 1
          if dist[nv] > d:
            cnt += 1
          stack.append(nv)
    return cnt
  ans = n
  if k%2 == 0:
    for i in range(n):
      ans = min(ans, dfs([i]))
  else:
    for l in E:
      ans = min(ans, dfs(l))
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
T = [[] for _ in range(n)]
E = []
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
  E.append((a, b))
d = k//2
def dfs(vs):
  dist = [-1]*n
  stack = []
  cnt = 0
  for v in vs:
    stack.append(v)
    dist[v] = 0
  while stack:
    v = stack.pop()
    for nv in T[v]:
      if dist[nv] == -1:
        dist[nv] = dist[v] + 1
        if dist[nv] > d:
          cnt += 1
        stack.append(nv)
  return cnt
ans = n
if k%2 == 0:
  for i in range(n):
    ans = min(ans, dfs([i]))
else:
  for l in E:
    ans = min(ans, dfs(l))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
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
    st = []
    st.append((p, v, d))
    while st:
        p, v, d = st.pop()
        if d > radius:
            ret += 1
        for nv in edge[v]:
            if nv == p:
                continue
            st.append((v, nv, d+1))
    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: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N, K = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append(b)
  e[b].append(a)
d = [[N for _ in range(N + 1)] for _ in range(N + 1)]
for s in range(1, N + 1):
  Q = dq([s])
  d[s][s] = 0
  while len(Q):
    p = Q.popleft()
    for q in e[p]:
      if d[s][q] > d[s][p] + 1:
        d[s][q] = d[s][p] + 1
        Q.append(q)
vis = set()
table = [[0] * (N + 1) for _ in range(N + 1)]
lntable = [0] * (N + 1)
for i in range(1, N + 1):
  for j in range(1, N + 1):
    if d[i][j] > K:
      table[i][j] = 1
      lntable[i] += 1
while True:
  t = 0
  for i in range(1, N + 1):
    if i in vis: continue
    if lntable[i] > lntable[t]: t = i
  if t == 0: break
  for i in range(1, N + 1):
    if table[i][t] == 1:
      table[i][t] = 0
      lntable[i] -= 1
  vis.add(t)
print(len(vis))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N, K = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  e[a].append(b)
  e[b].append(a)
d = [[N for _ in range(N + 1)] for _ in range(N + 1)]
for s in range(1, N + 1):
  Q = dq([s])
  d[s][s] = 0
  while len(Q):
    p = Q.popleft()
    for q in e[p]:
      if d[s][q] > d[s][p] + 1:
        d[s][q] = d[s][p] + 1
        Q.append(q)
vis = set()
table = [set() for _ in range(N + 1)]
for i in range(1, N + 1):
  for j in range(1, N + 1):
    if d[i][j] > K: table[i].add(j)
while True:
  t = 0
  for i in range(1, N + 1):
    if i in vis: continue
    if len(table[i]) > len(table[t]): t = i
  if t == 0: break
  for i in range(1, N + 1):
    table[i].discard(t)
  vis.add(t)
print(len(vis))

Submission status: Time Limit Exceeded

Solution code:
n,k = [int(i) for i in input().split()]
edges = [[int(i)-1 for i in input().split()] for j in range(n-1)]

node = [[] for _ in range(n)]
for edge in edges:
    node[edge[0]].append(edge[1])
    node[edge[1]].append(edge[0])

M = 0
for i in range(n):
    count = 1
    que = []
    check = [False]*n
    if k%2==0:
        check[i] = True
        que.append(i)
    elif i!=n-1:
        check[edges[i][0]]=True
        check[edges[i][1]]=True
        que.append(edges[i][0])
        que.append(edges[i][1])
        count = 2
    for j in range(k//2):
        newque = []
        while len(que)!=0:
            q = que.pop()
            for l in node[q]:
                if check[l]:
                    continue
                newque.append(l)
                check[l] = True
                count += 1
        que = newque
    M = max(M,count)
print(n-M)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n,k = [int(i) for i in input().split()]
edges = [[int(i)-1 for i in input().split()] for j in range(n-1)]

node = [[] for i in range(n)]
for edge in edges:
    node[edge[0]].append(edge[1])
    node[edge[1]].append(edge[0])

M = 0
for i in range(n):
    count = 1
    que = []
    check = [False for i in range(n)]
    if k%2==0:
        check[i] = True
        que.append(i)
    elif i!=n-1:
        check[edges[i][0]]=True
        check[edges[i][1]]=True
        que.append(edges[i][0])
        que.append(edges[i][1])
        count = 2
    for j in range(k//2):
        newque = []
        while len(que)!=0:
            q = que.pop()
            for l in node[q]:
                if check[l]:
                    continue
                newque.append(l)
                check[l] = True
                count += 1
        que = newque
    M = max(M,count)
print(n-M)

Submission status: Time Limit Exceeded

Solution code:
n,k = [int(i) for i in input().split()]
edges = [[int(i)-1 for i in input().split()] for j in range(n-1)]

node = [[] for i in range(n)]
for edge in edges:
    node[edge[0]].append(edge[1])
    node[edge[1]].append(edge[0])

M = 0
for i in range(n):
    count = 1
    que = []
    newque = []
    check = [False for i in range(n)]
    if k%2==0:
        check[i] = True
        que.append(i)
    elif i!=n-1:
        check[edges[i][0]]=True
        check[edges[i][1]]=True
        que.append(edges[i][0])
        que.append(edges[i][1])
        count = 2
    for j in range(k//2):
        while len(que)!=0:
            q = que.pop()
            for l in node[q]:
                if check[l]==True:
                    continue
                newque.append(l)
                check[l] = True
                count += 1
        que = newque
        newque = []
    M = max(M,count)
print(n-M)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,k = [int(i) for i in input().split()]
edges = [[int(i)-1 for i in input().split()] for j in range(n-1)]

node = [[] for i in range(n)]
for edge in edges:
    node[edge[0]].append(edge[1])
    node[edge[1]].append(edge[0])

M = 0
for i in range(n):
    count = 1
    que = deque()
    newque = deque()
    check = [False for i in range(n)]
    if k%2==0:
        check[i] = True
        que.append(i)
    elif i!=n-1:
        check[edges[i][0]]=True
        check[edges[i][1]]=True
        que.append(edges[i][0])
        que.append(edges[i][1])
        count = 2
    for j in range(k//2):
        while len(que)!=0:
            q = que.pop()
            for l in node[q]:
                if check[l]==True:
                    continue
                newque.append(l)
                check[l] = True
                count += 1
        que = newque
        newque = deque()
    M = max(M,count)
print(n-M)

Submission status: Time Limit Exceeded

Solution code:
import collections

n,k=map(int,input().split())
g=[[] for _ in range(n+1)]
e=[]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
  e.append((a,b))
ans=0
if k%2==0:
  for i in range(1,n+1):
    tmp=0
    checked=[0]*(n+1)
    checked[i]=1
    q=collections.deque()
    q.append((i,0))
    while len(q)!=0:
      v,d=q.popleft()
      if d<=k//2:
        tmp+=1
      else:
        break
      for u in g[v]:
        if checked[u]==0:
          checked[u]=1
          q.append((u,d+1))
    ans=max(ans,tmp)
  print(n-ans)
if k%2==1:
  for v1,v2 in e:
    tmp=0
    checked=[0]*(n+1)
    checked[v1]=1
    checked[v2]=1
    q=collections.deque()
    q.append((v1,0))
    while len(q)!=0:
      v,d=q.popleft()
      if d<=k//2:
        tmp+=1
      else:
        break
      for u in g[v]:
        if checked[u]==0:
          checked[u]=1
          q.append((u,d+1))
    checked=[0]*(n+1)
    checked[v1]=1
    checked[v2]=1
    q=collections.deque()
    q.append((v2,0))
    while len(q)!=0:
      v,d=q.popleft()
      if d<=(k-1)//2:
        tmp+=1
      else:
        break
      for u in g[v]:
        if checked[u]==0:
          checked[u]=1
          q.append((u,d+1))
    ans=max(ans,tmp)
  print(n-ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split()) # 横に2個

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

#print(graph)

dis = [[] for _ in range(N)]
for i in range(N):
    d = 0
    checked = [False for _ in range(N)]
    checked[i] = True
    qs = [i]
    #print(i)
    while qs:
        qqs = []
        for p in qs:
            for k in graph[p]:
                if not checked[k]:
                    checked[k] = True
                    qqs.append(k)
        d += 1
        if d > K and qqs:
            #print(d, qqs)
            for l in qqs:
                dis[i].append(l)
        qs = qqs

ans = 0
while True:
    end = True
    max = 0
    for i, d in enumerate(dis):
        if len(d) > 0:
            end = False
        if len(d) > max:
            rem = i
            max = len(d)
    if end:
        break
    for p in dis[rem]:
        dis[p].remove(rem)
    dis[rem] = []
    #print(rem)
    ans += 1
    #print(dis)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
from collections import defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, k = LI()

    G = defaultdict(list)
    AB = [LI_() for _ in range(n - 1)]
    for a, b in AB:
        G[a].append(b)
        G[b].append(a)

    def DFS(ss: list, t: int):
        # print([s + 1 for s in ss])
        q = deque()
        for s in ss:
            q.append((s, 0))
        visited = set(ss)
        cnt = 0
        while q:
            v, d = q.pop()
            visited.add(v)
            # print(v + 1, d)
            for to in G[v]:
                if to in visited:
                    continue
                if d + 1 > t:
                    cnt += 1
                q.append((to, d + 1))

        # print(cnt)
        return cnt

    # 木の性質
    # 直径をdとした時
    # dが偶数ならば，ある頂点vから他の頂点への距離がD/2となる頂点vが存在する
    # dが奇数ならば，ある辺eから他の頂点への距離が(D-1)/2となる辺eが存在する
    res = INF
    if k % 2:
        for a, b in AB:
            res = min(res, DFS([a, b], (k - 1) // 2))
    else:
        for i in range(n):
            res = min(res, DFS([i], k // 2))

    return res


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append((a-1,b-1))

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

sys.setrecursionlimit(4100000)

if k % 2 == 0:
    d = k//2
    ass = 2001
    for i in range(n):
        tmp = 0
        f(i,-1,0)
        ass = min(ass,tmp)
    print(ass)
else:
    d = (k-1)//2
    ass = 2001
    for e1 in alledge:
        tmp = 0
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        ass = min(ass,tmp)
    print(ass)