結果
問題 | No.2047 Path Factory |
ユーザー |
|
提出日時 | 2022-05-04 01:26:37 |
言語 | Kotlin (2.1.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 967 bytes |
コンパイル時間 | 11,213 ms |
コンパイル使用メモリ | 439,904 KB |
実行使用メモリ | 96,196 KB |
最終ジャッジ日時 | 2024-09-20 03:06:00 |
合計ジャッジ時間 | 29,260 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 RE * 8 |
ソースコード
fun main() {val n = readInt()val adj = Array(n) { mutableListOf<Int>() }for (i in 0 until n - 1) {val edge = readInts()val v1 = edge[0] - 1val v2 = edge[1] - 1adj[v1].add(v2)adj[v2].add(v1)}val mod = 998244353Lval dp = Array(n) { LongArray(3) { 0 } }fun dfs(v: Int, par: Int) {var p = 1Lvar s = 0Lvar t = 0Lfor (w in adj[v]) {if (w != par) {dfs(w, v)t = (t * (dp[w][1] + dp[w][2]) + s * (dp[w][0] + dp[w][1])) % mods = (s * (dp[w][1] + dp[w][2]) + p * (dp[w][0] + dp[w][1])) % modp *= dp[w][1] + dp[w][2]p %= mod}}dp[v][0] = pdp[v][1] = sdp[v][2] = t}dfs(0, -1)println((dp[0][1] + dp[0][2]) % mod)}fun readInt() = readln().toInt()fun readInts() = readln().split(" ").map { it.toInt() }