結果
問題 | No.2047 Path Factory |
ユーザー | 👑 rin204 |
提出日時 | 2022-08-19 22:11:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 279 ms / 2,000 ms |
コード長 | 922 bytes |
コンパイル時間 | 336 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 103,332 KB |
最終ジャッジ日時 | 2024-10-15 13:30:40 |
合計ジャッジ時間 | 5,661 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
MOD = 998244353 n = int(input()) edges = [[] for _ in range(n)] for _ in range(n - 1): u, v = map(int, input().split()) u -= 1 v -= 1 edges[u].append(v) edges[v].append(u) stack = [0] route = [0] used = [False] * n used[0] = True while stack: pos = stack.pop() for npos in edges[pos]: if used[npos]: continue used[npos] = True stack.append(npos) route.append(npos) dp1 = [0] * n dp2 = [0] * n used = [False] * n for pos in route[::-1]: used[pos] = True dp = [1, 0, 0] for npos in edges[pos]: if not used[npos]: continue ndp = [0] * 3 ndp[0] = dp[0] * dp1[npos] % MOD ndp[1] = (dp[1] * dp1[npos] + dp[0] * dp2[npos]) % MOD ndp[2] = (dp[2] * dp1[npos] + dp[1] * dp2[npos]) % MOD dp = ndp dp1[pos] = (dp[1] + dp[2]) % MOD dp2[pos] = (dp[0] + dp[1]) % MOD print(dp1[0])