提出 #24451348

---

ソースコード 拡げる

import sys
sys.setrecursionlimit(10**5)

def calc_dp(i, parent=-1):
  global children, dp_b, dp_w, mod
  if children[i] == [parent]: # bottom case
    return 1, 1

  result_w = 1
  result_b = 1
  for j in children[i]:
    if j == parent:
      continue
    result_w *= (dp_w[j] + dp_b[j])
    result_b *= dp_w[j]
    result_w %= mod
    result_b %= mod

  return result_b, result_w

def tree_search(i, parent=-1):
  global children, dp_b, dp_w
  for j in children[i]:
    if j == parent: # 親ノードはスキップする
      continue
    tree_search(j, i) # i を親ノードとして、子ノード j を処理する

  dp_b[i], dp_w[i] = calc_dp(i, parent) # dp_b[i], dp_w[i] を計算する関数

def main(f):
  global children, dp_b, dp_w, mod
  mod = 10**9 + 7
  N = int(f.readline())
  children = [[] for _ in range(N+1)]
  dp_b = [None] * (N+1) # db_b[i] : 親が Black の場合の i 以下のサブツリーの場合の数
  dp_w = [None] * (N+1) # db_w[i] : 親が Black の場合の i 以下のサブツリーの場合の数
  for _ in range(N-1):
    x, y = list(map(int, f.readline().split()))
    children[y].append(x)
    children[x].append(y)

  tree_search(1)
  print((dp_b[1] + dp_w[1]) % mod)

main(sys.stdin)

提出情報

ジャッジ結果