Submission #25089553

---

Source Code Expand

import sys, copy, heapq
from collections import defaultdict, deque


def main(f):
  mod = 10**9 + 7
  N = int(f.readline())
  children = [[] for _ in range(N+1)]
  for _ in range(N-1):
    x, y = map(int, f.readline().split())
    children[x].append(y)
    children[y].append(x)

  dp = [defaultdict(int) for _ in range(N+1)]
  q = deque()
  q.append((1, 0))
  while q:
    i, parent = q.pop()
    if i < 0:
      if children[-i] == [parent]:
        dp[-i]['b'] = 1
        dp[-i]['w'] = 1
        continue
      result_w = 1
      result_b = 1
      for j in children[-i]:
        if j == parent:
          continue
        result_w *= (dp[j]['b'] + dp[j]['w']) # 自分は while
        result_b *= dp[j]['w'] # 自分は black
        result_w %= mod
        result_b %= mod
      dp[-i]['b'] += result_b
      dp[-i]['w'] += result_w
      continue
    q.append((-i, parent))
    for j in children[i]:
      if j == parent:
        continue
      q.append((j, i))

  print((dp[1]['w']+dp[1]['b'])%mod)

main(sys.stdin)

Submission Info

Judge Result