Submission #783705

---

Source Code Expand

MOD = 10**9 + 7
n = gets.chomp.to_i
a, b = [], []
h = Hash.new {|hsh, key| hsh[key] = []}
(n-1).times do |i|
  a[i], b[i] = gets.chomp.split(" ").map(&:to_i)
  h[a[i]] << b[i]
  h[b[i]] << a[i]
end

def dp(n, p, hash)
  tmp = 1
  tmpW = 1
  hash[n].each do |i|
    if i == p
      next
    end
    t = dp(i, n, hash)
    tmpW *= t[0]
    tmp *= t[1]
  end
  return [(tmp + tmpW) % MOD, tmpW % MOD]
end

puts dp(1, 0, h)[0]

Submission Info

Judge Result