Submission #690647

---

Source Code Expand

N = gets.to_i
@bridge = {}
@dp = Array.new(10010)
@dp2 = Array.new(10010)

def f(p, x)
  child = @bridge[x].reject { |i| i == p }

  child.each { |j| f(x, j) } 

  prod = 1
  child.each { |j| prod *= @dp[j] }

  @dp2[x] = prod % 1000000007
  
  prod2 = 1
  child.each { |j| prod2 *= @dp2[j] }
  @dp[x] = (@dp2[x] + prod2) % 1000000007
end

$<.read.split(/\n/).map do |s|
  a, b = s.split.map(&:to_i)
  a -=1
  b -=1
  @bridge[a] ||= Array.new
  @bridge[a] << b;
  @bridge[b] ||= Array.new
  @bridge[b] << a;
end

f(-1, 0)
puts @dp[0]

Submission Info

Judge Result