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

Solution code:
from sys import stdin
def main(le=len):
    n, k = map(int, raw_input().split())
    a = []
    g = [[] for _ in xrange(n)]
    dat = map(int, stdin.read().split(), [10] * 2 * (n - 1))
    for i in xrange(n - 1):
        u, v = dat[i*2] - 1, dat[i*2+1] - 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 = 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[:]
    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: Accepted

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 = 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[:]
    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: Runtime Error

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 = dist[mm][0]
    seen, dist2 = bfs(v)
    if dist1[mm]<dist2[mm]:
        done.add(v)
    else:
        done.add(u)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = (1 << len(links)) - 1
    q = deque([(0, s, -1)])
    pop = q.popleft
    extend = q.extend
    while q:
        cost, v, p = pop()
        if cost > limit:
            break
        not_reachable ^= 1 << v
        cost += 1
        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 ab:
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

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

Solution code:
import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = (1 << len(links)) - 1
    q = deque([(0, s, -1)])
    pop = q.popleft
    extend = q.extend
    while q:
        cost, v, p = pop()
        if cost > limit:
            break
        not_reachable ^= 1 << v
        cost += 1
        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 = 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: Runtime Error

Solution code:
import sys
from collections import deque, defaultdict


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

Solution code:
#C
n,k = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(j) for j in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)    

def dfs(u, cost):
    if dist[u]>=0: #if searched already
        return     
    dist[u] = cost
    e = edges[u]
    for v in e:
        dfs(v, cost+1)
    
ans = n

#when k is even, we should think about each node
if k%2==0:
    for u in range(n):
        dist = [-1]*n #if -1, it means not visited yet
        dfs(u,0)

        cnt = 0
        for v in dist:
            if v<=(k//2):
                cnt += 1

        ans = min(ans, n-cnt)


#when k is even, we should think about each edge
else:
    for u,e in enumerate(edges):
        for v in e:
            cnt = 0
            
            dist = [-1]*n #if -1, it means not visited yet
            dist[v] = 0
            dfs(u,0)
            for v in dist:
                if v<=(k//2):
                    cnt += 1
                    
            dist = [-1]*n #if -1, it means not visited yet
            dist[u] = 0
            dfs(v,0)
            for v in dist:
                if v<=(k//2):
                    cnt += 1    
            
            cnt -= 2
                    
            ans = min(ans, n-cnt)

print(ans)

Submission status: Runtime Error

Solution code:
#C
n,k = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(j) for j in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)    

ans = n    
#when k is even, we should think about each node
if k%2==0:
    def dfs(u, cost):
        if dist[u]>=0: #if searched already
            return     
        dist[u] = cost
        e = edges[u]
        for v in e:
            dfs(v, cost+1)    

    for u in range(n):
        dist = [-1]*n #if -1, it means not visited yet
        dfs(u,0)

        cnt = 0
        for v in dist:
            if v>(k//2):
                cnt += 1

        ans = min(ans, cnt)

    print(ans)

#when k is even, we should think about each edge
else:
    def dfs(u, cost):
        if dist[u]>=0: #if searched already
            return     
        dist[u] = cost
        e = edges[u]
        for v in e:
            dfs(v, cost+1)  
            
    for u,e in enumerate(edges):
        for v in e:
            cnt = 0
            
            dist = [-1]*n #if -1, it means not visited yet
            dist[v] = 0
            dfs(u,0)
            for v in dist:
                if v>(k//2):
                    cnt += 1
                    
            dist = [-1]*n #if -1, it means not visited yet
            dist[u] = 0
            dfs(v,0)
            for v in dist:
                if v>(k//2):
                    cnt += 1    
                    
            ans = min(ans, cnt)
    
    print(ans)

Submission status: Runtime Error

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


def search(tree, pos, past=None, depth=0):
    """
    子孫ノードを探索して、最深のノードとその深さを返す
    """
    # 子ノードを探索する
    ress = []  # 子ノードの探索結果
    for next_node in tree[pos]:
        # next_nodeが親なら探索しない
        if next_node == past:
            continue
        res = search(tree, next_node, pos, depth + 1)
        ress.append(res)

    ress.sort(reverse=True)

    # 子ノードがいないならばこのノードとその深さを返す
    if len(ress) == 0:
        ress = [[depth, pos]]

    return ress[0]


def countChildren(tree, pos):
    """
    ノードposを根ノードとした場合の
    深さ毎のノードを数える
    """

    def dfs(tree, pos, child_list=[], past=None, depth=0):
        child_list += [0] * (depth + 1 - len(child_list))

        child_list[depth] += 1

        # 子ノードを探索する
        for next_node in tree[pos]:
            # next_nodeが親なら探索しない
            if next_node == past:
                continue
            dfs(tree, next_node, child_list, pos, depth + 1)

    child_list = []
    dfs(tree, pos, child_list)
    return child_list[:]


# 最遠頂点対 u,vと直径diameterを求める
_, u = search(tree, 0)
diameter, v = search(tree, u)

# u,vを頂点ノードとしたときの深さ毎のノードを数える
u_list = countChildren(tree, u)
v_list = countChildren(tree, v)

# 縮める木の直径の長さ
clip_len = max(diameter - k, 0)

u_ans = sum(u_list[-clip_len:])
v_ans = sum(v_list[-clip_len:])

print(min(u_ans, v_ans))

Submission status: Runtime Error

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


def search(tree, pos, past=None, depth=0):
    """
    子孫ノードを探索して、最深のノードとその深さを返す
    """
    # 子ノードを探索する
    ress = []  # 子ノードの探索結果
    for next_node in tree[pos]:
        # next_nodeが親なら探索しない
        if next_node == past:
            continue
        res = search(tree, next_node, pos, depth + 1)
        ress.append(res)

    ress.sort(reverse=True)

    # 子ノードがいないならばこのノードとその深さを返す
    if len(ress) == 0:
        ress = [[depth, pos]]

    return ress[0]


def countChildren(tree, pos):
    """
    ノードposを根ノードとした場合の
    深さ毎のノードを数える
    """

    def dfs(tree, pos, child_list=[], past=None, depth=0):
        child_list += [0] * (depth + 1 - len(child_list))

        child_list[depth] += 1

        # 子ノードを探索する
        for next_node in tree[pos]:
            # next_nodeが親なら探索しない
            if next_node == past:
                continue
            dfs(tree, next_node, child_list, pos, depth + 1)

    child_list = []
    dfs(tree, pos, child_list)
    return child_list[:]


# 最遠頂点対 u,vと直径diameterを求める
_, u = search(tree, 0)
diameter, v = search(tree, u)

# u,vを頂点ノードとしたときの深さ毎のノードを数える
u_list = countChildren(tree, u)
v_list = countChildren(tree, v)

removed_nodes = 0

while diameter > k:
    if u_list[-1] < v_list[-1]:
        removed_nodes += u_list[-1]
        u_list.pop()
    else:
        removed_nodes += v_list[-1]
        v_list.pop()
    diameter -= 1

print(removed_nodes)

Submission status: Runtime Error

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

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

Solution code:
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vecll v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}


#define INF 1e9+7
#define LLINF 1e18+7
#define N 250000
ll MOD=1e9+7;


vector<vec> G;
int n,k;
int dfs(int e,int x,int t);
int calc(int x){
    int res=INF;
    for(auto e:G[x]){
        res=min(n-1-dfs(e,x,1),res);
    }
    return res;
}

int dfs(int e,int x,int t){
    int res=1;
    if(t>k)return 0;
    for(auto s:G[e]){
        if(s==x)continue;
        res+=dfs(s,e,t+1);
    }
    return res;
}


main(){
    cin>>n>>k;
    G.resize(n+1);
    rep(i,n-1){
        int a=in(),b=in();
        G[a].pb(b);G[b].pb(a);
    }
    int ans=INF;
    rep2(i,1,n){
        ans=min(ans,calc(i));
    }
    cout<<ans<<endl;
}

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
INF = float("inf")
edges = [[] for i in range(n)]
ega = []

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


def dfs(v):
    d= [0] * n
    q=[v]
    visited = [0] * n
    while q:
        v=q.pop()
        visited[v] = 1
        visited.append(v)
        for i in edges[v]:
            if not visited[i]:
                d[i] = d[v] + 1
                q.append(i)
    return d

mi = INF
table = []
for i in range(n):
    table.append(dfs(i))

if k%2 == 0:
    for i in range(n):
        disi = table[i]
        c = 0
        for m in range(n):
            if disi[m] > k/2:
                c += 1
        if mi>c:
            mi = c
    print(mi)

else:
    for edge in ega:
        c = 0
        if table[edge[0]] + table[edge[1]] > k-1:
            c += 1
        if mi>c:
            mi = c
    print(mi)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
import numpy as np
INF = float("inf")
edges = [[] for i in range(n)]
ega = []

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


def dfs(v):
    visited  = []
    INF = float("inf")
    d=[INF for i in range(n)]
    q=[]
    d[v]=0
    q.append(v)
    while len(q):
        v=q.pop()
        visited.append(v)
        for i in edges[v]:
            if i not in visited:
                d[i] = d[v] + 1
                q.append(i)
            else:
                continue
    return d

mi = INF
table = []
for i in range(n):
    table.append(dfs(i))

if k%2 == 0:
    for i in range(n):
        disi = table[i]
        c = 0
        for m in range(n):
            if disi[m] > k/2:
                c += 1
        if mi>c:
            mi = c
    print(mi)

else:
    for edge in ega:
        c = 0
        if table[edge[0]] + table[edge[1]] > k-1:
            c += 1
        if mi>c:
            mi = c
    print(mi)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
G = [[] for i 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)


def dfs(u, par, d):
    global tmp
    if d > K // 2:
        tmp += 1

    for w in G[u]:
        if w == par:
            continue
        dfs(w, u, d + 1)


num = float("inf")
for i in range(N):
    tmp = 0
    dfs(i, -1, 0)
    num = min(num, tmp)

print(num)

Submission status: Runtime Error

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

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)

Submission status: Runtime Error

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:
                used[e] = 1
           f(e,x,c)


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

Submission status: Runtime Error

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

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


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


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])
        f(e1[1])
        res.append(sum(used))
    print(min(res))

Submission status: Runtime Error

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


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


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])
        f(e1[1],e1[0])
        res.append(sum(used))
    print(min(res))

Submission status: Runtime Error

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


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


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

Submission status: Runtime Error

Solution code:
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
    if len(edge)-1 >=x and x >= 0:
        for e in edge[x]:
            if e != y:
                if c > d and e >= 0 and e<= n-1:
                    used[e] = 1
                f(e,x,c)


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

Submission status: Runtime Error

Solution code:
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
    if len(edge)-1 >=x and x >= 0:
        for e in edge[x]:
            if e != y:
                if c > d:
                    used[e] = 1
                f(e,x,c)


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

Submission status: Runtime Error

Solution code:
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:
            #used[e] = 1
            f(e,x,c)


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

Submission status: Runtime Error

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


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

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

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:
        nag = [0]*n
        used = [0]*n
        g(e1[0],e1[1])
        g(e1[1],e1[0])
        res.append(sum(used))
    print(min(res))

Submission status: Runtime Error

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


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



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

Submission status: Runtime Error

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


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



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

Submission status: Runtime Error

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


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



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

Submission status: Runtime Error

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


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


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