Submission #851589

---

Source Code Expand

N = gets.chomp.to_i
AB = (N-1).times.map{ gets.chomp.split(" ").map(&:to_i) }
M = [[]]
N.times.map{ M << [] }
AB.each{|a,b| M[a] << b; M[b] << a }
MOD = 10 ** 9 + 7

def draw(from, n)
  if M[n].size == 1
    b, w = [1, 1]
  else
    b, w = M[n].map{|to|
      next if from == to
      to_b, to_w = draw(n, to)
      [to_w, to_w + to_b]
    }.compact.inject([1,1]){|r, bw|
      r = [r[0] * bw[0], r[1] * bw[1]]
      r
    }
  end
  return [b, w]
end

start = M.map.with_index.max{|a, b| a[0].size <=> b[0].size }[1]
b, w = draw(0, start)

puts (b + w) % MOD

Submission Info

Judge Result