Problem p02985 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def P(m, n):
    num = 1
    for i in range(n):
        num = (num*(m-i)) % INF
    return num


n, k = list(map(int, sys.stdin.readline().split()))
graph = [dict() for i in range(n)]
for i in range(n):
    graph[i]["eda"]=[]
for i in range(n - 1):
    a, b = list(map(int, sys.stdin.readline().split()))
    graph[a - 1]["eda"].append(b - 1)
    graph[b - 1]["eda"].append(a - 1)
ans = 1
check = [False] * n
stack = [0]
ans = 1
while len(stack) > 0:
    x = stack.pop()
    check[x] = True
    count = 0
    for i in graph[x]["eda"]:
        if not check[i]:
            count += 1
            stack.append(i)
    if x == 0:
        temp = P(k - 1, count)
        ans = (ans * temp) % INF
    else:
        temp = P(k - 2, count)
        ans = (ans * temp) % INF

print((ans * k) % INF)

Buggy submission (verdict: Runtime Error):
import sys
import math

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 9 + 7

def P(n, r):
    num = int(math.factorial(n) / math.factorial(n - r))
    return num



n, k = list(map(int, sys.stdin.readline().split()))
graph = [dict() for i in range(n)]
for i in range(n):
    graph[i]["eda"]=[]
for i in range(n - 1):
    a, b = list(map(int, sys.stdin.readline().split()))
    graph[a - 1]["eda"].append(b - 1)
    graph[b - 1]["eda"].append(a - 1)
ans = 1
check = [False] * n
stack = [0]
ans = 1
while len(stack) > 0:
    x = stack.pop()
    check[x] = True
    count = 0
    for i in graph[x]["eda"]:
        if not check[i]:
            count += 1
            stack.append(i)
    if x == 0:
        temp = P(k - 1, count)
        ans = (ans * temp) % INF
    else:
        temp = P(k - 2, count)
        ans = (ans * temp) % INF

print((ans * k) % INF)

Buggy submission (verdict: Runtime Error):
import sys
import math

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 9 + 7

def P(n, r):
    return math.factorial(n) // math.factorial(n - r)



n, k = list(map(int, sys.stdin.readline().split()))
graph = [dict() for i in range(n)]
for i in range(n):
    graph[i]["eda"]=[]
for i in range(n - 1):
    a, b = list(map(int, sys.stdin.readline().split()))
    graph[a - 1]["eda"].append(b - 1)
    graph[b - 1]["eda"].append(a - 1)
ans = 1
check = [False] * n
stack = [0]
ans = 1
while len(stack) > 0:
    x = stack.pop()
    check[x] = True
    count = 0
    for i in graph[x]["eda"]:
        if not check[i]:
            count += 1
            stack.append(i)
    if x == 0:
        temp = P(k - 1, count)
        ans = (ans * temp) % INF
    else:
        temp = P(k - 2, count)
        ans = (ans * temp) % INF

print((ans * k) % INF)

Buggy submission (verdict: Runtime Error):
mport sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))

ki = []

for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []

for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][0] - 1, ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][1] - 1, ab[i][0] - 1])

def P(m ,n):
    if m <= 0 or n <= 0:
        return 1
    else:
        num = 1
        for i in range(n):
            num *= m-i
        return num



total_num = K
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    for i in range(1, N):
        if K-1 < len(ki[i]["eda"]):
            break
        total_num *= P(K-2, len(ki[i]["eda"])-1)
        total_num = total_num % 1000000007
        if total_num == 0:
            break

print(total_num)

Buggy submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))

ki = []

for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []

for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][0] - 1, ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][1] - 1, ab[i][0] - 1])

def P(m ,n):
    if m <= 0 or n <= 0:
        return 0
    else:
        num = 1
        for i in range(n):
            num *= m-i
        return num

def saiki(i, base, ki):
    num = 1
    eda_num = len(ki[i]["eda"])-1
    if eda_num == 0:
        return num
    num *= P(K-2, eda_num)

    for edge in ki[i]["eda"]:
        if edge[1] != base:
            num *= saiki(edge[1], i, ki)
            num = num % 1000000007
            #print(num)

    return num

total_num = K * P(K-1, len(ki[0]["eda"]))
for edge in ki[0]["eda"]:
    total_num *= saiki(edge[1], 0, ki)
    total_num = total_num % 1000000007
    if total_num == 0:
        break

print(total_num)

Buggy submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
ab = []
for i in range(N - 1):
    ab.append(list(map(int, input().split())))
    ab[-1][0] -= 1
    ab[-1][1] -= 1

ki = []
for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []
    ki[-1]["No"] = []
    ki[-1]["iro"] = -1
    ki[-1]["one"] = []

for i in range(N - 1):
    ki[ab[i][0]]["eda"].append([ab[i][0], ab[i][1]])
    ki[ab[i][1]]["eda"].append([ab[i][1], ab[i][0]])
    ki[ab[i][0]]["one"].append(ab[i][1])
    ki[ab[i][1]]["one"].append(ab[i][0])



def tansaku(i, base, ki):
    num = 1
    for node in ki[i]["one"]:
        if ki[node]["iro"] != -1:
            ki[i]["No"].append(ki[node]["iro"])
        for nodenode in ki[node]["one"]:
            if ki[nodenode]["iro"] != -1 and node != i:
                ki[i]["No"].append(ki[node]["iro"])

    num *= K - len(ki[i]["No"])
    num = num % 1000000007
    if num == 0:
        return 0

    for j in range(K):
        if not j in ki[i]["No"]:
            ki[i]["iro"] = j
            break

    for node in ki[i]["one"]:
        if node != base:
            num *= tansaku(node, i, ki)
            num = num % 1000000007

    return num


num = K
ki[0]["iro"] = 0

for node in ki[0]["one"]:
    num *= tansaku(node, 0, ki)
    num = num % 1000000007

print(num)

Buggy submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))
    ab[-1][0] -= 1
    ab[-1][1] -= 1

ki = []
for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []
    ki[-1]["No"] = []
    ki[-1]["iro"] = -1
    ki[-1]["one"] = []
    ki[-1]["two"] = []

for i in range(N-1):
    ki[ab[i][0]]["eda"].append([ab[i][0], ab[i][1]])
    ki[ab[i][1]]["eda"].append([ab[i][1], ab[i][0]])
    ki[ab[i][0]]["one"].append(ab[i][1])
    ki[ab[i][1]]["one"].append(ab[i][0])
for i in range(N-1):
    ki[ab[i][0]]["two"].extend(ki[ab[i][1]]["one"])
    ki[ab[i][1]]["two"].extend(ki[ab[i][0]]["one"])


def tansaku(i, base, ki):
    num = 1
    for node in ki[i]["one"]:
        if ki[node]["iro"] != -1:
            ki[i]["No"].append(ki[node]["iro"])
    for node in ki[i]["two"]:
        if ki[node]["iro"] != -1 and node != i:
            ki[i]["No"].append(ki[node]["iro"])

    num *= K-len(ki[i]["No"])
    num = num % 1000000007
    if num == 0:
        return 0
    for j in range(K):
        if not j in ki[i]["No"]:
            ki[i]["iro"] = j
            break

    for node in ki[i]["one"]:
        if node != base:
            num *= tansaku(node, i, ki)
            num = num % 1000000007

    return num

num = K
ki[0]["iro"] = 0

for node in ki[0]["one"]:
    num *= tansaku(node, 0, ki)
    num = num % 1000000007

print(num)