Submission #694527


Source Code Expand

n = gets.to_i

G = Array.new(n).map { [] }
(n - 1).times {
    u, v = gets.split.map(&:to_i)
    G[u - 1] << v - 1
    G[v - 1] << u - 1
}

MOD = 10 ** 9 + 7
DP0 = [0] * n
DP1 = [0] * n

def dfs(curr, prev)
    DP0[curr] = 1
    DP1[curr] = 1

    G[curr].each {|nxt|
        next if nxt == prev
        dfs(nxt, curr)
        DP0[curr] *= DP0[nxt] + DP1[nxt]
        DP1[curr] *= DP0[nxt]
        DP0[curr] %= MOD
        DP1[curr] %= MOD
    }
end

dfs(0, -1)
puts (DP0[0] + DP1[0]) % MOD

Submission Info

Submission Time
Task D - 塗り絵
User xumpei
Language Ruby (2.3.3)
Score 100
Code Size 522 Byte
Status AC
Exec Time 442 ms
Memory 13948 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 18 ms 1788 KB
001.txt AC 18 ms 1788 KB
002.txt AC 339 ms 12540 KB
003.txt AC 430 ms 13948 KB
004.txt AC 294 ms 11388 KB
005.txt AC 417 ms 13948 KB
006.txt AC 388 ms 13436 KB
007.txt AC 419 ms 13948 KB
008.txt AC 302 ms 11900 KB
009.txt AC 415 ms 13820 KB
010.txt AC 311 ms 12028 KB
011.txt AC 442 ms 13692 KB
012.txt AC 256 ms 8828 KB
013.txt AC 416 ms 13948 KB
014.txt AC 211 ms 8188 KB
015.txt AC 418 ms 13948 KB
016.txt AC 268 ms 11004 KB
017.txt AC 430 ms 13820 KB
018.txt AC 92 ms 4604 KB
019.txt AC 419 ms 13948 KB
020.txt AC 61 ms 3196 KB
021.txt AC 428 ms 13820 KB