Problem p02985 (python)

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

sys.setrecursionlimit(100005)

n, k = na()
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = na()
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

mod = 10**9 + 7


def dfs(cur, par, k, g):
    ret = 1
    nc = 0 if par == -1 else 1
    for e in g[cur]:
        if e == par: continue
        nc += 1
        ret = ret * (k - nc) % mod
        ret = ret * dfs(e, cur, k, g) % mod
    return ret % mod


print(dfs(0, -1, k, g) * k % mod)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)

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

mod = 10**9 + 7

p = [1] * (k - 1)  # {k-2}_P_{i} for i=0,1,...,k-2
for i in range(1, k - 1):
    p[i] = (p[i - 1] * (k - 1 - i)) % mod

g = [[] for _ in range(n + 1)]

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

node_left = set([i for i in range(1, n + 1)])

root = max(1, n // 2)


def dfs(t):
    if t == root:
        node_left.remove(t)
        children = g[t]
        if len(children) + 1 > k:
            return 0
        else:
            ret = k * (k - 1) * p[len(children) - 1]
            for c in children:
                node_left.remove(c)
                ret = (ret * dfs(c)) % mod
            return ret
    else:
        children = []
        for u in g[t]:
            if u in node_left:
                children.append(u)
                node_left.remove(u)
        if len(children) + 2 > k:
            return 0
        else:
            ret = p[len(children)]
            for c in children:
                ret = (ret * dfs(c)) % mod

            return ret


print(dfs(root))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)

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

mod = 10**9 + 7

p = [1] * (k - 1)  # {k-2}_P_{i} for i=0,1,...,k-2
for i in range(1, k - 1):
    p[i] = (p[i - 1] * (k - 1 - i)) % mod

g = [[] for _ in range(n + 1)]

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

used = [False] * (n + 1)


def dfs(t):
    if t == 1:
        used[0], used[1] = True, True
        num_children = len(g[1])
        if num_children + 1 > k:
            return 0
        else:
            ret = k * (k - 1) * p[num_children - 1]
            for c in g[t]:
                used[c] = True
                ret = (ret * dfs(c)) % mod
            return ret
    else:
        children = []
        for u in g[t]:
            if not used[u]:
                children.append(u)
                used[u] = True
        num_children = len(children)
        if num_children + 2 > k:
            return 0
        else:
            ret = p[num_children]
            for c in children:
                ret = (ret * dfs(c)) % mod

            return ret


print(dfs(1))

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())

mod = 10**9 + 7

p = [1] * (k - 1)  # {k-2}_P_{i} for i=0,1,...,k-2
for i in range(1, k - 1):
    p[i] = (p[i - 1] * (k - 1 - i)) % mod

# tree = [[-1, []] for _ in range(n + 1)]

# for _ in range(n - 1):
#     a, b = map(int, input().split())
#     if a > b:
#         a, b = b, a

#     tree[b][0] = a
#     tree[a][1].append(b)

g = [[] for _ in range(n + 1)]

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

used = [False] * (n + 1)


def dfs(t):
    if t == 1:
        used[0], used[1] = True, True
        num_children = len(g[1])
        if num_children + 1 > k:
            return 0
        else:
            ret = k * (k - 1) * p[num_children - 1]
            for c in g[t]:
                used[c] = True
                ret = (ret * dfs(c)) % mod
            return ret
    else:
        children = []
        for u in g[t]:
            if not used[u]:
                children.append(u)
                used[u] = True
        num_children = len(children)
        if num_children + 2 > k:
            return 0
        else:
            ret = p[num_children]
            for c in children:
                ret = (ret * dfs(c)) % mod

            return ret


print(dfs(1))