Submission #709189

---

Source Code Expand

n = gets.to_i
$links = Hash.new { |hash, key| hash[key] = [] }
(n - 1).times do
    a, b = gets.split().map { |e| e.to_i - 1 }
    $links[a] = $links[a] << b
    $links[b] = $links[b] << a
end
$w_dp = Array.new(n, 0)
$b_dp = Array.new(n, 0)
$searched = Array.new(n, false)
$mod = 10 ** 9 + 7

def search(i)
    if $w_dp[i] > 0 && $b_dp[i] > 0
        return $w_dp[i], $b_dp[i]
    end
    $searched[i] = true
    white = 1
    black = 1
    $links[i].each do |j|
        if !$searched[j]
            w, b = search(j)
            white *= w + b
            white %= $mod
            black *= w
            black %= $mod
        end
    end
    $w_dp[i] = white
    $b_dp[i] = black
    return white, black
end

w, b = search(0)
puts ((w + b) % $mod)

Submission Info

Judge Result