結果

問題 No.2047 Path Factory
コンテスト
ユーザー norioc
提出日時 2025-04-08 21:19:09
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,240 bytes
コンパイル時間 439 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 96,816 KB
最終ジャッジ日時 2025-04-08 21:19:18
合計ジャッジ時間 7,794 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

MOD = 998244353
N = int(input())
adj = defaultdict(list)
for i in range(N-1):
    u, v = map(lambda x: int(x)-1, input().split())
    adj[u].append(v)
    adj[v].append(u)


def tree_dp(v, par):
    dp0 = 1  # 頂点 v は孤立点
    dp1 = 0  # 頂点 v は端点
    dp2 = 0  # 頂点 v は中間点

    for to in adj[v]:
        if to == par: continue

        r_dp0, r_dp1, r_dp2 = tree_dp(to, v)
        pp0 = pp1 = pp2 = 0
        dp0, pp0 = pp0, dp0
        dp1, pp1 = pp1, dp1
        dp2, pp2 = pp2, dp2
        # v は孤立点のまま : 孤立点 * (端点 or 中間点)
        dp0 += pp0 * (r_dp1 + r_dp2)
        # v は端点のまま : 端点 * (端点 or 中間点)
        dp1 += pp1 * (r_dp1 + r_dp2)
        # v は中間点のまま : 中間点 * (端点 or 中間点)
        dp2 += pp2 * (r_dp1 + r_dp2)
        # v を孤立点から端点へ : 孤立点 * (孤立点 or 端点)
        dp1 += pp0 * (r_dp0 + r_dp1)
        # v を端点から中間点へ : 端点 * (孤立点 or 端点)
        dp2 += pp1 * (r_dp0 + r_dp1)

        dp0 %= MOD
        dp1 %= MOD
        dp2 %= MOD

    return dp0, dp1, dp2


_, dp1, dp2 = tree_dp(0, -1)
ans = (dp1 + dp2) % MOD
print(ans)
0