Submission #690200

---

Source Code Expand

# encoding: utf-8
@m = 1000000000+7
n = gets.chomp.to_i

@a = Array.new(n)
0.step(n-1, 1) do |i|
  @a[i] = Array.new
end
0.step(n-2, 1) do |i|
  ai,bi = gets.chomp.split(" ").map(&:to_i)
  @a[ai-1].push (bi-1)
  @a[bi-1].push (ai-1)
end

def bt(c, p)
  w = b = 1
  for v in @a[c]
    if v != p
      wc,bc = bt(v, c)
      w = w*(wc+bc)%@m
      b = b*wc%@m
    end
  end
  return [w, b]
end

r = (bt(0,-1).inject(:+))%@m
puts r

Submission Info

Judge Result