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:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append((a-1,b-1))
if n==2:
    print(0)
    exit()


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

sys.setrecursionlimit(4100000)

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

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


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

sys.setrecursionlimit(5000000)

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

Submission status: Time Limit Exceeded

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


def f(x,y,c):
    c += 1
    for e in edge[x]:
        if e != y:
            if c > d and e >= 0 and e<= n-1:
                used[e] = 1
            if len(edge[e])>=2:
                f(e,x,c)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans,c = [[] for i in range(n)],[[] for i in range(n)],n,0
for i,j in b:
	x[i].append(j)
	x[j].append(i)
for i in x: c = max(len(i),c)
if n-c+1<=k: ans = 0
elif k==1: ans = n-2
else:
	for i in range(n):
		q,v = deque(),[1]*n
		v[i] = 0
		for j in x[i]:
			q.append((j,1,j))
			d[i].append(j)
			v[j] = 0
		while q:
			p = q.pop()
			if p[1]<k//2:
				for j in x[p[0]]:
					if v[j]:
						q.append((j,p[1]+1,p[2]))
						d[i].append(p[2])
						v[j] = 0
	if k%2:
		for i,j in b: ans = min(ans,n-len(d[i])-len(d[j])+d[i].count(j)+d[j].count(i)-2)
	else:
		for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans = [[] for i in range(n)],[[] for i in range(n)],n
for i,j in b:
	x[i].append(j)
	x[j].append(i)
def f(s):
	for i in range(n):
		q,v = deque(),[1]*n
		v[i] = 0
		for j in x[i]:
			q.append((j,1,j))
			d[i].append(j)
			v[j] = 0
		while q:
			p = q.pop()
			if p[1]<s:
				for j in x[p[0]]:
					if v[j]:
						q.append((j,p[1]+1,p[2]))
						d[i].append(p[2])
						v[j] = 0
if k==1: ans = n-2
elif k%2:
	f((k-1)//2)
	for i in range(n-1):
		d1,d2 = d[b[i][0]],d[b[i][1]]
		ans = min(ans,n-len(d1)-len(d2)+d1.count(b[i][1])+d2.count(b[i][0])-2)
else:
	f(k//2)
	for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans = [[] for i in range(n)],[[None]*n for i in range(n)],n
for i,j in b:
	x[i].append(j)
	x[j].append(i)
for i in range(n):
	q,v,d[i][i] = [],[1]*n,(0,-1)
	v[i] = 0
	for j in x[i]:
		q.append((j,1,j))
		d[i][j],v[j] = (1,j),0
	while q:
		p = q.pop()
		for j in x[p[0]]:
			if v[j]:
				q.append((j,p[1]+1,p[2]))
				d[i][j],v[j] = (p[1]+1,p[2]),0
if k%2:
	for i in range(n-1):
		a = n
		for j,j2 in d[b[i][0]]:
			if b[i][1]!=j2 and (k-1)//2>=j: a-=1
		for j,j2 in d[b[i][1]]:
			if b[i][0]!=j2 and (k-1)//2>=j: a-=1
		ans = min(a,ans)
else:
	for i in range(n):
		a = n
		for j,j2 in d[i]:
			if j<=k//2: a-=1
		ans = min(a,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans = [[] for i in range(n)],[[None]*n for i in range(n)],n
for i,j in b:
	x[i].append(j)
	x[j].append(i)
for i in range(n):
	q,v,d[i][i] = [],[1]*n,(0,-1)
	v[i] = 0
	for j in x[i]:
		q.append((j,1,j))
		d[i][j],v[j] = (1,j),0
	while q:
		p = q.pop()
		for j in x[p[0]]:
			if v[j]:
				q.append((j,p[1]+1,p[2]))
				d[i][j],v[j] = (p[1]+1,p[2]),0
if k%2:
	for i in range(n-1):
		a = n
		for j,j2 in d[b[i][0]]:
			if b[i][1]!=j2 and (k-1)//2>=j: a-=1
		for j,j2 in d[b[i][1]]:
			if b[i][0]!=j2 and (k-1)//2>=j: a-=1
		ans = min(a,ans)
else:
	for i in range(n): ans = min(ans,n-bisect_left(sorted(d[i]),(k//2+1,0)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def bfs(graph:list, start:int) -> list:
    # 未探索のノードは距離null
    node = len(graph)
    dist = [None]*node
    
    # 始点ノードの距離を0とし、bfsのためのqueueを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    # kより大きいの距離のものを数える
    while que:
        cost, cur_node = que.popleft()

        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] is not None:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist

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

ans = n
# kが奇数の時
if k%2:
    for a,b in edges:
        dist1 = bfs(adj_list, a)
        dist2 = bfs(adj_list, b)
        ans = min(ans, sum([min(d1,d2) > (k-1)//2 for d1,d2 in zip(dist1, dist2)]))
    
# kが偶数の時
else:
    for st in range(n):
        dist = bfs(adj_list, st)
        ans = min(ans, sum([d > k//2 for d in dist]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def bfs(graph:list, node:int, start:int, k:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    # kより大きいの距離のものを数える
    cnt = 0
    while que:
        cost, cur_node = que.popleft()
        
        if cost > k:
            cnt += 1
        
        
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist,cnt


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


# bfs
ans = n
if k%2 == 0:
    for st in range(n):
        _, cnt = bfs(adj_list, n, st, k//2)
        ans = min(ans, cnt)
        
else:
    for st in range(n):
        for cost, to in adj_list[st]:
            if to <= st:
                continue
            
            dist1, _ = bfs(adj_list, n, st, (k-1)//2)
            dist2, _ = bfs(adj_list, n, to, (k-1)//2)
            cnt = 0
            
            for d1, d2 in zip(dist1, dist2):
                if min(d1,d2) > (k-1)//2:
                    cnt += 1
                    
            ans = min(ans, cnt)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
P=[-1 for i in range(N)]
rnk=[-1 for i in range(N)]
q=[0]
rnk[0]=0
while(len(q)>0):
    r=q[-1];q.pop()
    for p in G[r]:
        if rnk[p]!=-1:
            continue
        rnk[p]=rnk[r]+1
        P[p]=r
        q.append(p)
S=[[] for i in range(N)]
for i in range(N):
    S[i].append(P[i])
while(True):
    tmp=[0 for i in range(N)]
    flag=0
    for i in range(N):
        if S[i][-1]==-1:
            tmp[i]=-1
        else:
            flag=1
            tmp[i]=S[S[i][-1]][-1]
    if flag==0:
        break
    for i in range(N):
        S[i].append(tmp[i])
#pのk個上（存在しない場合は-1）
def bef(p,k):
    if rnk[p]<k:
        return -1
    else:
        m=str(bin(k))[2:][::-1]
        n=len(m)
        res=p
        for i in range(n):
            if m[i]=="1":
                res=S[res][i]
        return res
M=len(S[0])
def dist(x,y):
    if rnk[x]>rnk[y]:
        return (rnk[x]-rnk[y])+dist(bef(x,rnk[x]-rnk[y]),y)
    elif rnk[x]<rnk[y]:
        return (rnk[y]-rnk[x])+dist(x,bef(y,rnk[y]-rnk[x]))
    else:
        if x==y:
            return 0
        res=0
        tmpx=x
        tmpy=y
        while(True):
            j=0
            if tmpx==tmpy:
                return res
            for i in range(M-1):
                if S[tmpx][i]!=S[tmpy][i] and S[tmpx][i+1]==S[tmpy][i+1]:
                    j=i
                    break
            res+=2**(j+1)
            tmpx=S[tmpx][i]
            tmpy=S[tmpy][i]
'''
X=max(rnk)
leaf=[]
for i in range(N):
    if rnk[i]==X:
        leaf.append(i)
'''
d=[[dist(i,j) for i in range(N)] for j in range(N)]
#dia=max([max([d[i][j] for i in range(N)]) for j in range(N)])
if K%2==0:
    t=[[d[i][j] for i in range(N)] for j in range(N)]
    D=K//2
    ans=[0 for i in range(N)]
    for i in range(N):
        for j in range(N):
            if t[i][j]>D:
                ans[i]+=1
    print(min(ans))
else:
    t=[[min([d[a[i]][j],d[b[i]][j]]) for j in range(N)] for i in range(N-1)]
    ans=[0 for i in range(N-1)]
    D=(K-1)//2
    for i in range(N-1):
        for j in range(N):
            if t[i][j]>D:
                ans[i]+=1
    print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
P=[-1 for i in range(N)]
rnk=[-1 for i in range(N)]
q=[0]
rnk[0]=0
while(len(q)>0):
    r=q[-1];q.pop()
    for p in G[r]:
        if rnk[p]!=-1:
            continue
        rnk[p]=rnk[r]+1
        P[p]=r
        q.append(p)
S=[[] for i in range(N)]
for i in range(N):
    S[i].append(P[i])
while(True):
    tmp=[0 for i in range(N)]
    flag=0
    for i in range(N):
        if S[i][-1]==-1:
            tmp[i]=-1
        else:
            flag=1
            tmp[i]=S[S[i][-1]][-1]
    if flag==0:
        break
    for i in range(N):
        S[i].append(tmp[i])
#pのk個上（存在しない場合は-1）
def bef(p,k):
    if rnk[p]<k:
        return -1
    else:
        m=str(bin(k))[2:][::-1]
        n=len(m)
        res=p
        for i in range(n):
            if m[i]=="1":
                res=S[res][i]
        return res
M=len(S[0])
def dist(x,y):
    if rnk[x]>rnk[y]:
        return (rnk[x]-rnk[y])+dist(bef(x,rnk[x]-rnk[y]),y)
    elif rnk[x]<rnk[y]:
        return (rnk[y]-rnk[x])+dist(x,bef(y,rnk[y]-rnk[x]))
    else:
        if x==y:
            return 0
        res=0
        tmpx=x
        tmpy=y
        while(True):
            j=0
            if tmpx==tmpy:
                return res
            for i in range(M-1):
                if S[tmpx][i]!=S[tmpy][i] and S[tmpx][i+1]==S[tmpy][i+1]:
                    j=i
                    break
            res+=2**(j+1)
            tmpx=S[tmpx][i]
            tmpy=S[tmpy][i]
'''
X=max(rnk)
leaf=[]
for i in range(N):
    if rnk[i]==X:
        leaf.append(i)
'''
d=[[dist(i,j) for i in range(N)] for j in range(N)]
#dia=max([max([d[i][j] for i in range(N)]) for j in range(N)])
if K%2==0:
    t=[[d[i][j] for i in range(N)] for j in range(N)]
    D=K//2
    ans=[0 for i in range(N)]
    for i in range(N):
        for j in range(N):
            if t[i][j]>D:
                ans[i]+=1
    print(min(ans))
else:
    t=[[min([d[a[i]][j],d[b[i]][j]]) for j in range(N)] for i in range(N-1)]
    ans=[0 for i in range(N-1)]
    D=(K-1)//2
    for i in range(N-1):
        for j in range(N):
            if t[i][j]>D:
                ans[i]+=1
    print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, K = map(int, input().split())
T = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    E.append([a, b])


def bfs(n):
    visited = [False] * N
    dist = [0] * N
    queue = deque([n])
    while queue:
        node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        for n in T[node]:
            if not visited[n]:
                dist[n] = dist[node] + 1
                queue.appendleft(n)
    return dist


dist = []
for i in range(N):
    dist.append(bfs(i))

ans = float('inf')
if K % 2 == 0:
    for i in range(N):
        ans = min(ans, len([d for d in dist[i] if d > K / 2]))

else:
    for a, b in E:
        ans = min(ans, len([d for d in [min(d1, d2) for d1, d2 in zip(dist[a], dist[b])] if d> (K-1) / 2]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, K = map(int, input().split())
T = [[] for i in range(N)]
E = []
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    T[a].append(b)
    T[b].append(a)
    E.append((a, b))


def bfs(n):
    visited = [False] * N
    dist = [0] * N
    queue = deque([n])
    while queue:
        node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        for n in T[node]:
            if not visited[n]:
                dist[n] = dist[node] + 1
                queue.appendleft(n)
    return dist


dist = []
for i in range(N):
    dist.append(bfs(i))

ans = float('inf')
if K % 2 == 0:
    # 全ての頂点について全探索
    for i in range(N):
        ans = min(ans, len([d for d in dist[i] if d > K / 2]))
else:
    # 全ての辺について全探索
    for a, b in E:
        adist = [(1 if min(d1, d2) > (K-1) / 2 else 0) for d1, d2 in zip(dist[a], dist[b])]
        ans = min(ans, sum(adist))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
E = [set() for i in range(N+1)]
Er = []
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)
    Er.append({a, b})
ma = 0
Start = []
if K&1 == 1:
    Start = Er
else:
    Start = [{i} for i in range(1, N+1)]
for st in Start:
    L = list(st)
    Closed = st
    for j in range(K//2):
        S = []
        for l in L:
            S += E[l]
        L = []
        for s in S:
            if s not in Closed:
                L.append(s)
                Closed.add(s)
    ma = max(ma, len(Closed))
print(N-ma)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)


def dfs(v, parent, rest, edge):
    ret = 0
    for c in edge[v]:
        if c != parent:
            ret += dfs(c, v, rest - 1, edge)
    return ret + (rest <= 0)


def main(N, K, edge):
    ans = N
    if K % 2 == 0:
        for v in range(N):
            ans = min(ans, sum(dfs(c, v, K // 2, edge) for c in edge[v]))
    else:
        for v in range(N):
            for c in edge[v]:
                ans = min(ans, dfs(v, c, K // 2 + 1, edge) + dfs(c, v, K // 2 + 1, edge))
    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        edge[u].append(v)
        edge[v].append(u)
    main(N, K, edge)

Submission status: Time Limit Exceeded

Solution code:
o=lambda:map(int,raw_input().split())
T,F=True,False
n,k=o()
e=[[] for _ in [0]*n]
for _ in [0]*(n-1):a,b=o();e[a-1]+=[b-1];e[b-1]+=[a-1]
a=10**5
def dfs(x,f):
 if f>=0:l[f]=T
 q=[(x,0)]
 while len(q):
  v,c=q.pop(0)
  if c>k/2:break
  l[v]=T
  for w in e[v]:
   if ~l[w]:q+=[(w,c+1)]
 return n-l.count(T)
if k%2:
 for i in range(n):
  for j in e[i]:
   if i<j:l=[F]*n;dfs(i,j);a=min(a,dfs(j,i))
else:
 for i in range(n):l=[F]*n;a=min(a,dfs(i,-1))
print a

Submission status: Time Limit Exceeded

Solution code:
o=lambda:map(int,raw_input().split())
T,F=True,False
n,k=o()
e=[[] for _ in [0]*n]
exec('a,b=o();e[a-1]+=[b-1];e[b-1]+=[a-1];'*(n-1))
a=10**5
def dfs(x,f):
 if f>=0:l[f]=T
 q=[(x,0)]
 while len(q):
  v,c=q.pop(0)
  if c>k/2:break
  l[v]=T
  for w in e[v]:
   if ~l[w]:q+=[(w,c+1)]
 return n-l.count(T)
if k%2:
 for i in range(n):
  for j in e[i]:
   if i<j:l=[F]*n;dfs(i,j);a=min(a,dfs(j,i))
else:
 for i in range(n):l=[F]*n;a=min(a,dfs(i,-1))
print a

Submission status: Time Limit Exceeded

Solution code:
ii=lambda:map(int,raw_input().split())
n,k=ii()
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=ii()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
cost=[0]*n
ans=10**5
def dfs(x,f):
    if f>=0:vis[f]=True
    q=[(x,0)]
    while len(q):
        v,c=q.pop(0)
        if c>k/2:break
        cost[v]=c;vis[v]=True
        for w in e[v]:
            if not vis[w]:q+=[(w,c+1)]
    return n-vis.count(True)
if k%2:
    for i in range(n):
        for j in e[i]:
            if i<j:vis=[False]*n;dfs(i,j);ans=min(ans,dfs(j,i))
    print ans
else:
    for i in range(n):vis=[False]*n;ans=min(ans,dfs(i,-1))
    print ans

Submission status: Time Limit Exceeded

Solution code:
ii=lambda:map(int,raw_input().split())
n,k=ii()
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=ii()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
cost=[0]*n
ans=10**5
visit=[0]
def dfs(x,f):
    global visit
    del visit[:]
    visit+=[f]
    q=[(x,0)]
    while len(q):
        v,c=q.pop(0);cost[v]=c;visit+=[v]
        for w in e[v]:
            if w not in visit:q+=[(w,c+1)]
    return len([i for i in cost if i>k/2])
if k%2:
    for i in range(n):
        for j in e[i]:
            if i<j:dfs(i,j);ans=min(ans,dfs(j,i))
    print ans
else:
    for i in range(n):
        ans=min(ans,dfs(i,-1))
    print ans

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

d = [0] * n
e = [[-1 for i in range(n)] for j in range(n)]

def dfs(i):
    for j in e[i]:
        if j < 0:
            continue
        if d[j] < 0:
            d[j] = d[i] + 1
            dfs(j)

for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1

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

ans = n

if k % 2 == 0:
    for i in range(n):
        for j in range(n):
            d[j] = -1
        d[i] = 0
        dfs(i)

        cnt = 0
        for j in range(n):
            if d[j] > k // 2:
                cnt += 1
        ans = min(ans, cnt)

else:
    for i in range(n):
        for j in e[i]:
            if j < -1 or i > j:
                continue

            for l in range(n):
                d[l] = -1
            d[i] = 0
            d[j] = 0
            dfs(i)
            dfs(j)

            cnt = 0
            for l in range(n):
                if d[l] > (k - 1) // 2:
                    cnt += 1
            ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

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

def bfs1(c):
    visited[c]=1
    q=deque([c])
    while len(q)>0:
        p=q.popleft()
        for i in v[p]:
            if visited[i]==0:
                q.append(i)
                visited[i]=1
                d[c][i]=d[c][p]+1

def bfs2(c1,c2):
    visited[c2]=1
    bfs1(c1)
    bfs1(c2)

n,k=map(int,raw_input().split())
d=[[0]*n for _ in xrange(n)]
v=[[] for _ in xrange(n)]
e=[]
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    v[a].append(b)
    v[b].append(a)
    e.append([a,b])
if k%2==0:
    min_del=1000000
    for i in xrange(n):
        cnt=0
        visited=[0]*n
        bfs1(i)
        for j in xrange(n):
            if d[i][j]>k/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)
else:
    min_del=1000000
    for i,j in e:
        cnt=0
        visited=[0]*n
        d=[[0]*n for _ in xrange(n)]
        bfs2(i,j)
        for l in xrange(n):
            if d[i][l]>(k-1)/2 or d[j][l]>(k-1)/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)

Submission status: Time Limit Exceeded

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

def dfs1(s,c):
    visited[s]=1
    for i in v[s]:
        if visited[i]==0:
            d[c][i]=d[c][s]+1
            dfs1(i,c)
    return

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

n,k=map(int,raw_input().split())
d=[[0]*n for _ in xrange(n)]
v=[[] for _ in xrange(n)]
e=[]
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    v[a].append(b)
    v[b].append(a)
    e.append([a,b])
if k%2==0:
    min_del=1000000
    for i in xrange(n):
        cnt=0
        visited=[0]*n
        dfs1(i,i)
        for j in xrange(n):
            if d[i][j]>k/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)
else:
    min_del=1000000
    for i,j in e:
        cnt=0
        visited=[0]*n
        d=[[0]*n for _ in xrange(n)]
        dfs2(i,j)
        for l in xrange(n):
            if d[i][l]>(k-1)/2 or d[j][l]>(k-1)/2:
                cnt+=1
        min_del=min(min_del,cnt)
    print(min_del)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
# 参考：https://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf
# 参考：http://yambe2002.hatenablog.com/entry/2016/07/17/050852

import sys


REC_LIMIT = 10000
UNDEF = -1


def min_vertices_to_remove(n, k, adj_edges):
    def count_dfs(current, previous, distance):
        result = int(distance > k // 2)
        for next_vertex in adj_edges[current]:
            if next_vertex == previous:
                continue
            else:
                result += count_dfs(next_vertex, current, distance + 1)
        return result
    if k % 2 == 0:
        ans = min(count_dfs(v, UNDEF, 0) for v in range(n))
    else:
        ans = min(min(count_dfs(v, w, 0) + count_dfs(w, v, 0)
                  for w in adj_edges[v]) for v in range(n))
    return ans


def main():
    sys.setrecursionlimit(REC_LIMIT)
    n, k = map(int, input().split())
    adj_edges = [set() for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        adj_edges[a].add(b)
        adj_edges[b].add(a)
    print(min_vertices_to_remove(n, k, adj_edges))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(bfr,h,dist,E,rad,ne):
	cnt = 1
	if dist < rad:
		for nxt in E[h]:
			if nxt == bfr: continue
			cnt += rad_reach(h,nxt,dist+1,E,rad,ne) 
	return cnt
def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [set() for i in xrange(N)]
	for i in xrange(N-1):
		a,b = map(lambda x:int(x)-1,raw_input().split())
		E[a].add(b)
		E[b].add(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:
			E[c1].remove(c2); E[c2].remove(c1)
			ans = min(ans,N-rad_reach(-1,c1,0,E,rad,c2)-rad_reach(-1,c2,0,E,rad,c1))
			E[c1].add(c2); E[c2].add(c1)
	print ans
solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
# 参考：http://yambe2002.hatenablog.com/entry/2016/07/17/050852

import sys


REC_LIMIT = 10000
UNDEF = -1


def min_vertices_to_remove(n, k, adj_edges):
    def count_dfs(current, previous, distance):
        result = int(distance > k // 2)
        for next_vertex in adj_edges[current]:
            if next_vertex == previous:
                continue
            else:
                result += count_dfs(next_vertex, current, distance + 1)
        return result
    if k % 2 == 0:
        ans = min(count_dfs(v, UNDEF, 0) for v in range(n))
    else:
        ans = min(min(count_dfs(v, w, 0) + count_dfs(w, v, 0)
                  for w in adj_edges[v]) for v in range(n))
    return ans


def main():
    sys.setrecursionlimit(REC_LIMIT)
    n, k = map(int, input().split())
    adj_edges = [set() for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        adj_edges[a].add(b)
        adj_edges[b].add(a)
    print(min_vertices_to_remove(n, k, adj_edges))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(b,h,dist,E,rad,ne):
	cnt = 1
	if dist < rad:
		for nxt in E[h]:
			if nxt == b or nxt == ne:
				continue
			cnt += rad_reach(h,nxt,dist+1,E,rad,ne) 
	return cnt
def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [[] for i in xrange(N)]
	for i in xrange(N-1):
		a,b = map(lambda x:int(x)-1,raw_input().split())
		E[a].append(b)
		E[b].append(a)
		pairs.append((a,b))
	ans = N
	rad = K/2
	if K % 2 == 0:
		for c in xrange(N):
			ans = min(ans,N-rad_reach(-1,c,0,E,rad,-1))
	else:
		for c1,c2 in pairs:
			ans = min(ans,N-rad_reach(-1,c1,0,E,rad,c2)-rad_reach(-1,c2,0,E,rad,c1))
	print ans
solve()

Submission status: Time Limit Exceeded

Solution code:
def calc_dist(b,h,dist,E,D,ne):
	D[dist] += 1
	for nxt in E[h]:
		if nxt == b or nxt == ne:
			continue
		calc_dist(h,nxt,dist+1,E,D,ne) 

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 i in xrange(N):
			D = [0]*N
			calc_dist(-1,i,0,E,D,-1)
			for j in xrange(rad):
				D[rad-j-1] += D[rad-j]
			ans = min(N-D[0],ans)
	else:
		for a,b in pairs:
			D1 = [0]*N
			D2 = [0]*N
			calc_dist(-1,a,0,E,D1,b)
			calc_dist(-1,b,0,E,D2,a)
			for j in xrange(rad):
				D1[rad-j-1] += D1[rad-j]
				D2[rad-j-1] += D2[rad-j]
			ans = min(N-D1[0]-D2[0],ans)
	print ans

solve()

Submission status: Time Limit Exceeded

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


def dfs(x, fa, d):
    if d > K:
        return 0
    sz = 1
    for v in tree[x]:
        if v != fa:
            sz += dfs(v, x, d + 1)
    return sz

ans = N
if K % 2 == 0:
    K //= 2
    for i in range(N):
        # print(i, N - dfs(i, 0, 0))
        ans = min(ans, N - dfs(i, 0, 0))
    print(ans)
else:
    K //= 2
    for x in range(N):
        for v in tree[x]:
            ans = min(ans, N - dfs(x, v, 0) - dfs(v, x, 0))
    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)
dias_lst = []
for i in range(N):
    dias = [-1 for _ in range(N)]
    dfs(i, 0)
    dias_lst.append(list(dias))

if K % 2 == 0:
    for i in range(N):
        over_count = sum([1 if x > K / 2 else 0 for x in dias_lst[i]])
        ans = min(ans, over_count)
    print(ans)
else:
    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)