Problem p04049 (python)

Fixed submission:
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)

Buggy submission (verdict: Runtime Error):
#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)

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
#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))

Buggy submission (verdict: Runtime Error):
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))