結果
問題 | No.2214 Products on Tree |
ユーザー |
|
提出日時 | 2022-11-25 04:53:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,470 ms / 3,000 ms |
コード長 | 1,336 bytes |
コンパイル時間 | 328 ms |
コンパイル使用メモリ | 82,160 KB |
実行使用メモリ | 444,520 KB |
最終ジャッジ日時 | 2024-10-07 08:57:14 |
合計ジャッジ時間 | 26,691 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import sysfrom collections import deque, Countersys.setrecursionlimit(5 * 10 ** 5)from pypyjit import set_paramset_param('max_unroll_recursion=-1')input = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())mi = lambda: map(int, input().split())li = lambda: list(mi())inf = 2 ** 63 - 1mod = 998244353def solve(n, AB):dp = [[0] * 2 for _ in range(n)]s = set()graph = [[] for _ in range(n)]for a, b in AB:graph[a - 1].append(b - 1)graph[b - 1].append(a - 1)s.add(0)def dfs(now):dp[now][0] = dp[now][1] = 1des = []for to in graph[now]:if to not in s:des.append(to)s.add(to)dfs(to)for to in des:dp[now][0] *= (dp[to][0] + dp[to][1])dp[now][0] %= modP = dp[now][0]dp[now][1] = Pfor to in des:P *= pow(dp[to][0] + dp[to][1], mod - 2, mod)P %= modP *= dp[to][1]P %= moddp[now][1] += Pdp[now][1] %= modP *= pow(dp[to][1], mod - 2, mod)P %= modP *= (dp[to][0] + dp[to][1])P %= moddfs(0)return dp[0][1]n = ii()AB = [li() for _ in range(n - 1)]print(solve(n, AB))