Submission #851597

---

Source Code Expand

class Node
  attr_reader :children, :value
  def initialize(v)
    @value = v
    @children = []
  end

  def add(other)
    @children << other
  end

  def count_white(from)
    targets = @children.reject { |n| n.value == from }
    @count_white ||=
      if targets.empty?
        1
      else
        targets.map{|n| n.count_white(@value) + n.count_black(@value) }.inject(:*)
      end
  end

  def count_black(from)
    targets = @children.reject { |n| n.value == from }
    @count_black ||= targets.map { |n| n.count_white(@value) }.inject(:*) || 1
  end
end

N = gets.to_i
nodes = Array.new(N) { |i| Node.new(i+1) }
(N-1).times do
  a, b = gets.split.map(&:to_i)
  va, vb = nodes[a-1], nodes[b-1]
  va.add(vb)
  vb.add(va)
end

root = nodes.first
p (root.count_white(root.value) + root.count_black(root.value)) % ((10 ** 9) + 7)

Submission Info

Judge Result