Problem p02985 (python)

Fixed submission:
from collections import defaultdict, deque
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, K = map(int, input().split())
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]

log = [float('inf')]*N
log[0] = 0
q = deque([0])
ans = K
while q:
  p = q.popleft()
  if log[p]<1:
    ans *= cmb(K-1,K-1-len(dic[p]),mod)
  else:
    ans *= cmb(K-2,K-1-len(dic[p]),mod)
  ans %= mod
  for e in dic[p]:
    if log[e]>log[p]+1:
      q += [e]
      log[e] = log[p]+1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict, deque
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, K = map(int, input().split())
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]

log = [float('inf')]*N
log[0] = 0
q = deque([0])
ans = K
while q:
  p = q.popleft()
  if log[p]<1:
    ans *= cmb(K-1,K-1-len(dic[p]),mod)
  else:
    ans *= cmb(K-2,K-1-len(dic[p]),mod)
  ans %= mod
  for e in dic[p]:
    if log[e]>log[p]+1:
      q += [e]
      log[e] = log[p]+1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
MOD = 10**9+7
N, K = map(int, input().split())
es = defaultdict(list)

for i in range(N-1):
  a, b = map(int, input().split())
  es[a-1] += [b-1]
  es[b-1] += [a-1]
  
def dfs(now, par):
  if par==-1:
    can_use = K-1
  else:
    can_use = K-2
  if K<len(es[now]):
    return 0
  else:
    case_num = 1
    for e in es[now]:
      if e==par:
        continue
      case_num *= can_use
      can_use -= 1
      case_num %= MOD
    for e in es[now]:
      if e==par:
        continue
      case_num *= dfs(e, now)
      case_num %= MOD
    return case_num

ans = K*dfs(0,-1)
ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
MOD = 10**9+7
N, K = map(int, input().split())
es = defaultdict(list)

for i in range(N-1):
  a, b = map(int, input().split())
  es[a-1] += [b-1]
  es[b-1] += [a-1]
  
def dfs(now, par):
  if par==-1:
    can_use = K-1
  else:
    can_use = K-2
  if K<len(es[now]):
    return 0
  else:
    case_num = 1
    for e in es[now]:
      if e==par:
        continue
      case_num *= can_use
      can_use -= 1
      case_num %= MOD
    for e in es[now]:
      if e==par:
        continue
      case_num *= dfs(e, now)
      case_num %= MOD
    return case_num

ans = K*dfs(a-1,-1)
ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
MOD = 10**9+7
N, K = map(int, input().split())
E = defaultdict(list)

for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1] += [b-1]
  E[b-1] += [a-1]
  
def dfs(K, es, now, par):
  if par==-1:
    can_use = K-1
  else:
    can_use = K-2
  if K<len(es[now]):
    return 0
  else:
    case_num = 1
    for e in es[now]:
      if e==par:
        continue
      case_num *= can_use
      can_use -= 1
      case_num %= MOD
    for e in es[now]:
      if e==par:
        continue
      case_num *= dfs(K, es, e, now)
      case_num %= MOD
    return case_num

ans = K*dfs(K, E, 0,-1)
ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
MOD = 10**9+7
N, k = map(int, input().split())
E = defaultdict(list)

for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1] += [b-1]
  E[b-1] += [a-1]
  
def dfs(K, es, now, par):
  if par==-1:
    can_use = K-1
  else:
    can_use = K-2
  if K<len(es[now]):
    return 0
  else:
    case_num = 1
    for e in es[now]:
      if e==par:
        continue
      case_num *= can_use
      can_use -= 1
      case_num %= MOD
    for e in es[now]:
      if e==par:
        continue
      case_num *= dfs(e, now)
      case_num %= MOD
    return case_num

ans = k*dfs(k, E, 0,-1)
ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
MOD = 10**9+7
N, K = map(int, input().split())
es = defaultdict(list)

for i in range(N-1):
  a, b = map(int, input().split())
  es[a-1] += [b-1]
  es[b-1] += [a-1]
  
def dfs(now, par):
  if par==-1:
    can_use = K-1
  else:
    can_use = K-2
  if can_use+1<len(es[now]):
    return 0
  else:
    case_num = 1
    for e in es[now]:
      if e==par:
        continue
      case_num *= can_use
      can_use -= 1
      case_num %= MOD
    for e in es[now]:
      if e==par:
        continue
      case_num *= dfs(e, now)
      case_num %= MOD
    return case_num

ans = K*dfs(0,-1)
ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
MOD = 10**9+7
N, K = map(int, input().split())
es = defaultdict(list)

for i in range(N-1):
  a, b = map(int, input().split())
  es[a-1] += [b-1]
  es[b-1] += [a-1]
  
def dfs(now, par):
  if par==-1:
    can_use = K-1
  else:
    can_use = K-2
  if K<len(es[now]):
    return 0
  else:
    case_num = 1
    for e in es[now]:
      if e==par:
        continue
      case_num *= can_use
      can_use -= 1
      case_num %= MOD
    for e in es[now]:
      if e==par:
        continue
      case_num *= dfs(e, now)
      case_num %= MOD
    return case_num

ans = K*dfs(0,-1)
ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
MOD = 10**9+7
N, K = map(int, input().split())
es = defaultdict(list)

for i in range(N-1):
  a, b = map(int, input().split())
  es[a-1] += [b-1]
  es[b-1] += [a-1]
  
def dfs(now, par):
  if par==-1:
    can_use = K-1
  else:
    can_use = K-2
  if K<len(es[now]):
    return 0
  else:
    case_num = 1
    for e in es[now]:
      if e==par:
        continue
      case_num *= can_use
      can_use -= 1
      case_num %= MOD
    for e in es[now]:
      if e==par:
        continue
      case_num *= dfs(e, now)
      case_num %= MOD
  return case_num

ans = K*dfs(0,-1)
ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from operator import mul
from functools import reduce
MOD = 10**9+7
N, K = map(int, input().split())
es = defaultdict(list)
log = [1]*N

for i in range(N-1):
  a, b = map(int, input().split())
  es[a-1] += [b-1]
  es[b-1] += [a-1]
  
if K==1:
  print(0)
  
else:
  stuck = []
  log[a-1] = 0
  ans = K
  n = 0
  for c in es[a-1]:
    log[c] = 0
    n += 1
    stuck += [c]
  if K-1<n:
    print(0)
  else:
    ans *= reduce(mul, range(K-1, K-1-n, -1))
    while stuck:
      e = stuck.pop()
      n = 0
      for c in es[e]:
        if log[c]:
          stuck += [c]
          n += 1
          log[c] = 0
      if K-2<n:
        ans *= 0
        break
      elif n==0:
        continue
      else:
        ans *= reduce(mul, range(K-2, K-2-n, -1))
      ans %= MOD
    print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from operator import mul
from functools import reduce
def p(n,r):
  if r==0:
    return 1
  return reduce(mul, range(n, n-r, -1))
MOD = 10**9+7
N, K = map(int, input().split())
es = defaultdict(list)
log = [1]*N

for i in range(N-1):
  a, b = map(int, input().split())
  es[a-1] += [b-1]
  es[b-1] += [a-1]

stuck = [a-1]
log[a-1] = 0
ans = K
while stuck:
  e = stuck.pop()
  n = 0
  for c in es[e]:
    if log[c]:
      stuck += [c]
      n += 1
      log[c] = 0
  if e==a-1:
    ans *= p(K-1, n)
  elif K-2<n:
    ans *= 0
    break
  else:
    ans *= p(K-2, n)
  ans %= MOD
print(ans)