Problem p02985 (python)

Fixed submission:
import queue

n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))
mod = 10**9+7

edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()
q = queue.LifoQueue()
q.put(1)

num_cases = 1
while not q.empty():
  node = q.get()
  
  visited.add(node)
  num_available_colors = k -2 if node is not 1 else k -1
  
  for child in (edge_dict[node] - visited):
    num_cases *= num_available_colors
    num_available_colors -= 1
    num_cases %= mod
    q.put(child)

print((k*num_cases)%mod)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000)

n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

mod = 10**9+7
edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()

def visit(node, parent):
  for child in edge_dict[node]:
    if not child is parent:
      visit(child, node)

print(visit(1, None))

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()

def dfs(node, parent):
  for child in edge_dict[node]:
    if child is parent:
      continue
    
    dfs(child, node)
  
  return k

print(dfs(1, None))

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()

def visit(node, parent):
  ans = 1
  for child in edge_dict[node]:
    if not child is parent:
      ans = (ans * visit(child, node))%mod
  
  return k

print(visit(1, None))

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))


mod = 10**9+7
edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()

def visit(node, parent):
  num_children = len(edge_dict[node])
  num_available_colors = k-2 if parent is not None else k-1
  
  if k < num_children:
    return 0
  
  ans = 1
  for child in edge_dict[node]:
    if child is parent:
      continue
    
    ans *= num_available_colors
    num_available_colors -= 1
    ans %= mod
  
  for child in edge_dict[node]:
    if child is parent:
      continue
    
    ans *= visit(child, node)
    ans %= mod
  
  return ans

print((k*visit(1, None))%mod)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

mod = 10**9+7
edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()

def visit(node, parent):
  num_children = len(edge_dict[node])
  num_available_colors = k-2 if parent is not None else k-1
  
  if num_available_colors < num_children:
    return 0
  
  ans = 1
  for child in edge_dict[node]:
    if child is parent:
      continue
    
    ans *= num_available_colors
    num_available_colors -= 1
    ans %= mod
  
  for child in edge_dict[node]:
    if child is parent:
      continue
    
    ans *= visit(child, node)
    ans %= mod
  
  return ans

print((k*visit(1, None))%mod)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

# n = 16
# k = 22
# edges = list(map(lambda x: list(map(int, x.split())), """12 1
# 3 1
# 4 16
# 7 12
# 6 2
# 2 15
# 5 16
# 14 16
# 10 11
# 3 10
# 3 13
# 8 6
# 16 8
# 9 12
# 4 3""".split("\n")))

# n = 5
# k = 4
# edges = list(map(lambda x: list(map(int, x.split())), """1 2
# 1 3
# 1 4
# 4 5""".split("\n")))

mod = 10**9+7
edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

# print(edge_dict)
visited = set()

def visit(node, parent):
  num_children = len(edge_dict[node])
  num_available_colors = k-2 if parent is not None else k-1
  
  if num_available_colors < num_children:
    return 0
  
  ans = 1
  
#   print("VISIT {} {} {}".format(node, ans, num_available_colors))
  for child in edge_dict[node]:
    if child is parent:
      continue
    
    ans *= num_available_colors
    num_available_colors -= 1
    ans %= mod
  
#   print("VISIT {} {} {}".format(node, ans, num_available_colors))
  
  for child in edge_dict[node]:
    if child is parent:
      continue
    
    ans *= visit(child, node)
    ans %= mod
  
#   print("VISIT {} from {}, {}, {}".format(node, parent, ans, num_children))
  return ans

print((k*visit(1, None))%mod)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
mod = 10**9+7
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()

def visit(node, parent):
  if parent is not None:
    ans = (k - 1 - len(visited & (edge_dict[parent])))
  else:
    ans = k
  
  visited.add(node)
  
  for child in edge_dict[node]:
    if not child is parent:
      ans = (ans * visit(child, node))%mod
  
  return ans

print(visit(1, None))

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
mod = 10**9+7
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()

def visit(node, parent):
  if parent is not None:
    ans = (k - 1 - len(visited & (edge_dict[parent])))
  else:
    ans = k
  
  visited.add(node)
  
  for child in edge_dict[node]:
    if not child is parent:
      ans = (ans * visit(child, node))%mod
  
  print("Visit {} {}".format(node, ans))
  return ans

print(visit(1, None))

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
mod = 10**9+7
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()
ans = 1
def visit(node, parent, grand_parent):
  global ans
  if parent is not None:
    ans = (ans * (k - 1 - len(visited & (edge_dict[parent]))))%mod
  else:
    ans = (ans * k)%mod
  
  visited.add(node)
  
  for child in (edge_dict[node] - visited):
    visit(child, node, parent)

visit(1, None, None)
print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
mod = 10**9+7
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()
ans = 1
def visit(node, parent, grand_parent):
  global ans
  if parent is not None:
    ans = (ans * (k - 1 - len(visited & (edge_dict[parent]))))%mod
  else:
    ans = (ans * k)%mod
  
  visited.add(node)
  
  for child in edge_dict[node]:
    if not child in visited:
      visit(child, node, parent)

visit(1, None, None)
print(ans)