Submission #714561

---

Source Code Expand

n = gets.to_i
$a = []
$fa = [false] * (n+1)
(n+1).times do
  $a << []
end
(n-1).times do
  s, e = gets.split.map(&:to_i)
  $a[s] << e
  $a[e] << s
end

def solve(i)
  $fa[i] = true
  s = b = 1
  $a[i].each do |ai|
    next if $fa[ai]
    ns, nb = solve(ai)
    s *= ns
    b *= nb
  end
  return [s+b, s]
end
p solve(1)[0] % (10**9+7)

Submission Info

Judge Result