Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split()) # 横に2個
L = [list(map(int, input().split())) for _ in range(N-1)]

mod = 10**9+7

neardic = {}
checked = {}
for p in range(1, N+1):
    near = []
    for l in L:
        if p in l:
            other = set(l) - {p}
            near.append(list(other)[0])
    neardic[p] = set(near)
    checked[p] = False


def color(p=1, state=[1], prob=K, checked=checked):
    checked[p] = True
    nears = neardic[p]
    leaf = True
    for near in nears:
        if not checked[near]:
            leaf = False
            break
    if leaf:
        state.pop()
        return prob
    
    nextprobmax = K-1 if len(state) == 1 else K-2
    c = 0
    for i, near in enumerate(nears):
        if checked[near]:
            c += 1
            continue
        prob = prob * (nextprobmax - i + c) % mod
        state.append(near)
        prob = color(near, state, prob, checked)
    return prob

print(color())

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

checked = [False]*N
C = [None]*N
checked[0] = True

def dfs(p, c1, c2, depth):
    C[p] = c1 + c2
    d = 0
    for np in graph[p]:
        if not checked[np]:
            checked[np] = True
            d += 1
            g = 1 if depth > 0 else 0
            dfs(np, d, g, depth+1)
        

dfs(0, 0, 0, 0)
#print(C)

mod = 10**9+7
ans = 1
for n in range(N):
    ans = ans * (K-C[n]) % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split()) # 横に2個
L = [list(map(int, input().split())) for _ in range(N-1)]

mod = 10**9+7

neardic = {}
for p in range(1, N+1):
    near = []
    for l in L:
        if p in l:
            other = set(l) - {p}
            near.append(list(other)[0])
    neardic[p] = set(near)

def color(p=1, state=[1], prob=K, checked=set()):
    nears = neardic[p]
    checked.add(p)
    # bottle neck
    unchecked_nears = nears - checked
    A = len(unchecked_nears)
    if A == 0:
        state.pop()
        return prob
    nextprobmax = K-1 if len(state) == 1 else K-2
    for i, near in enumerate(unchecked_nears):
        prob = prob * (nextprobmax - i) % mod
        state.append(near)
        prob = color(near, state, prob, checked)
    return prob

print(color())




Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

checked = [False]*N
C = [None]*N
checked[0] = True

def dfs(p, c1, c2, depth):
    C[p] = c1 + c2
    d = 0
    for np in graph[p]:
        if not checked[np]:
            checked[np] = True
            d += 1
            g = 1 if depth > 0 else 0
            dfs(np, d, g, depth+1)
        

dfs(0, 0, 0, 0)
#print(C)

mod = 10**9+7
ans = 1
for n in range(N):
    ans = ans * (K-C[n]) % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split()) # 横に2個
L = [list(map(int, input().split())) for _ in range(N-1)]

mod = 10**9+7

neardic = {}
for p in range(1, N+1):
    near = []
    for l in L:
        if p in l:
            other = set(l) - {p}
            near.append(list(other)[0])
    neardic[p] = set(near)


def color(p=1, state=[1], prob=K, checked=set()):
    nears = neardic[p]
    checked.add(p)
    unchecked_nears = nears - checked
    A = len(unchecked_nears)
    if A == 0:
        state.pop()
        return prob
    nextprobmax = K-1 if len(state) == 1 else K-2
    for i, near in enumerate(unchecked_nears):
        prob = prob * (nextprobmax - i) % mod
        state.append(near)
        prob = color(near, state, prob, checked)
    return prob

print(color())




Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

checked = [False]*N
C = [None]*N
checked[0] = True

def dfs(p, c1, c2, depth):
    C[p] = c1 + c2
    d = 0
    for np in graph[p]:
        if not checked[np]:
            checked[np] = True
            d += 1
            g = 1 if depth > 0 else 0
            dfs(np, d, g, depth+1)
        

dfs(0, 0, 0, 0)
#print(C)

mod = 10**9+7
ans = 1
for n in range(N):
    ans = ans * (K-C[n]) % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split()) # 横に2個
L = [list(map(int, input().split())) for _ in range(N-1)]

mod = 10**9+7

neardic = {}
for p in range(1, N+1):
    near = []
    for l in L:
        if p in l:
            other = set(l) - {p}
            near.append(list(other)[0])
    neardic[p] = set(near)


def color(p=1, state=[1], prob=K, checked=set()):
    nears = neardic[p]
    checked.add(p)
    unchecked_nears = nears - checked
    A = len(unchecked_nears)
    if A == 0:
        return prob
    nextprobmax = K-1 if len(state) == 1 else K-2
    for i, near in enumerate(unchecked_nears):
        prob = prob * (nextprobmax - i) % mod
        nowstate = state[:]
        nowstate.append(near)
        prob = color(near, nowstate, prob, checked)
    return prob

print(color())




Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

checked = [False]*N
C = [None]*N
checked[0] = True

def dfs(p, c1, c2, depth):
    C[p] = c1 + c2
    d = 0
    for np in graph[p]:
        if not checked[np]:
            checked[np] = True
            d += 1
            g = 1 if depth > 0 else 0
            dfs(np, d, g, depth+1)
        

dfs(0, 0, 0, 0)
#print(C)

mod = 10**9+7
ans = 1
for n in range(N):
    ans = ans * (K-C[n]) % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split()) # 横に2個
L = [list(map(int, input().split())) for _ in range(N-1)]

mod = 10**9+7

neardic = {}
for p in range(1, N+1):
    near = []
    for l in L:
        if p in l:
            other = set(l) - {p}
            near.append(list(other)[0])
    neardic[p] = near


def color(p=1, state=[1], prob=K, checked=[]):
    nears = neardic[p]
    checked.append(p)
    unchecked_nears = set(nears) - set(checked)
    A = len(unchecked_nears)
    if A == 0:
        return prob
    if len(state) == 1:
        nextprobmax = K-1
    else:
        nextprobmax = K-2
    for i, near in enumerate(unchecked_nears):
        prob = prob * (nextprobmax - i) % mod
        nowstate = state[:]
        nowstate.append(near)
        prob = color(near, nowstate, prob, checked)
    return prob

print(color())




Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

checked = [False]*N
C = [None]*N
checked[0] = True

def dfs(p, c1, c2, depth):
    C[p] = c1 + c2
    d = 0
    for np in graph[p]:
        if not checked[np]:
            checked[np] = True
            d += 1
            g = 1 if depth > 0 else 0
            dfs(np, d, g, depth+1)
        

dfs(0, 0, 0, 0)
#print(C)

mod = 10**9+7
ans = 1
for n in range(N):
    ans = ans * (K-C[n]) % mod

print(ans)