Submission #24450734

---

Source Code Expand

import sys
from functools import lru_cache
sys.setrecursionlimit(10**5)

@lru_cache(maxsize=None)
def solve(i, black=True, parent=-1):
  global children, mod
  if children[i] == [parent]:
    return 1

  result = 1
  for j in children[i]:
    if j == parent:
      continue
    c = solve(j, False, i) # white
    if not black:
      c += solve(j, True, i) # black
    result *= c
    result %= mod
  return result

def main(f):
  global children, mod
  mod = 10**9 + 7

  N = int(f.readline())
  children = [[] for _ in range(N+1)]
  for _ in range(N-1):
    x, y = list(map(int, f.readline().split()))
    children[y].append(x)
    children[x].append(y)

  print((solve(1, True) + solve(1, False)) % mod)

main(sys.stdin)

Submission Info

Judge Result