Submission #24470146

---

Source Code Expand

import sys
from collections import defaultdict, deque

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 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_order を用意する
  tree_order = deque()
  q = deque()
  q.append((1, -1))
  while q:
    i, parent = q.pop()
    tree_order.append((i, parent))
    for j in children[i]:
      if j == parent:
        continue
      q.append((j, i))

  # tree_order を右から順に処理する
  while tree_order:
    i, parent = tree_order.pop()
    dp_b[i], dp_w[i] = calc_dp(i, parent) # dp_b[i], dp_w[i] を計算する関数

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

main(sys.stdin)

Submission Info

Judge Result