結果
問題 |
No.2047 Path Factory
|
ユーザー |
![]() |
提出日時 | 2022-09-18 22:10:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 336 ms / 2,000 ms |
コード長 | 1,715 bytes |
コンパイル時間 | 251 ms |
コンパイル使用メモリ | 82,260 KB |
実行使用メモリ | 107,844 KB |
最終ジャッジ日時 | 2024-12-22 01:41:09 |
合計ジャッジ時間 | 6,304 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import sys from operator import itemgetter from collections import defaultdict, deque import heapq from heapq import heapify, heappop, _heapify_max, heappush from bisect import bisect_left, bisect_right import math import itertools import copy stdin=sys.stdin #sys.setrecursionlimit(10 ** 7) ## import pypyjit ## pypyjit.set_param('max_unroll_recursion=-1') ip=lambda: int(sp()) fp=lambda: float(sp()) lp=lambda:list(map(int,stdin.readline().split())) sp=lambda:stdin.readline().rstrip() Yp=lambda:print('Yes') Np=lambda:print('No') inf = 1 << 60 mod = 10 ** 9 + 7 mod = 998244353 eps = 1e-9 sortkey1 = itemgetter(0) sortkey2 = lambda x: (x[0], x[1]) ############################################################### N = ip() adj = [[] for _ in range(N)] for _ in range(N - 1): u, v = lp() u -= 1; v -= 1 adj[u].append(v) adj[v].append(u) dp = [[0 for _ in range(3)] for _ in range(N)] visit = [False for _ in range(N)] start = 0 deq = deque([(~start, -1), (start, -1)]) while deq: now, par = deq.pop() ## 行きがけ if now >= 0: visit[now] = True for nex in adj[now]: if visit[nex]: continue deq.append((~nex, now)) deq.append((nex, now)) ## 帰りがけ else: x0 = 1; x1 = 0; x2 = 0 for ch in adj[~now]: if ch != par: x2 = (x2 * (dp[ch][1] + dp[ch][2]) + x1 * (dp[ch][0] + dp[ch][1])) % mod x1 = (x0 * (dp[ch][0] + dp[ch][1]) + x1 * (dp[ch][1] + dp[ch][2])) % mod x0 = x0 * (dp[ch][1] + dp[ch][2]) % mod dp[~now][0] = x0 dp[~now][1] = x1 dp[~now][2] = x2 ans = dp[0][1] + dp[0][2] ans %= mod print(ans)