Submission #1513105


Source Code Expand

MOD = 1_000_000_007

N = gets.to_i
R = Hash.new {|h, k| h[k] = []}
(N - 1).times do
  a, b = gets.split.map(&:to_i)
  R[a] << b
  R[b] << a
end

C = [0, Array.new(N + 1), Array.new(N + 1)]

#  1 : white
# -1 : black

def calc(node, from, color)
  return C[color][node] if C[color][node]
  if R[node].size == 1 && R[node][0] == from
    return C[color][node] = 1
  else
    ans = 1
    R[node].each do |x|
      next if x == from
      if color == 1
        ans *= (calc(x, node, -1) + calc(x, node, 1))
      else
        ans *= calc(x, node, 1)
      end
      ans %= MOD
    end
    return C[color][node] = ans
  end
end

puts (calc(1, 0, 1) + calc(1, 0, - 1)) % MOD

Submission Info

Submission Time
Task D - 塗り絵
User hatovalley
Language Ruby (2.3.3)
Score 100
Code Size 702 Byte
Status AC
Exec Time 409 ms
Memory 21012 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 22
Set Name Test Cases
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt
Case Name Status Exec Time Memory
000.txt AC 7 ms 1788 KB
001.txt AC 7 ms 1788 KB
002.txt AC 304 ms 16892 KB
003.txt AC 368 ms 18940 KB
004.txt AC 248 ms 12540 KB
005.txt AC 377 ms 19068 KB
006.txt AC 358 ms 20092 KB
007.txt AC 398 ms 18940 KB
008.txt AC 271 ms 14076 KB
009.txt AC 392 ms 18940 KB
010.txt AC 274 ms 14460 KB
011.txt AC 405 ms 18812 KB
012.txt AC 225 ms 11644 KB
013.txt AC 370 ms 18940 KB
014.txt AC 173 ms 12284 KB
015.txt AC 386 ms 18940 KB
016.txt AC 229 ms 11772 KB
017.txt AC 374 ms 18812 KB
018.txt AC 69 ms 4988 KB
019.txt AC 409 ms 18940 KB
020.txt AC 40 ms 3708 KB
021.txt AC 371 ms 21012 KB