結果

問題 No.2677 Minmax Independent Set
ユーザー nu50218
提出日時 2023-12-01 01:13:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 650 ms / 2,000 ms
コード長 886 bytes
コンパイル時間 798 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 122,996 KB
最終ジャッジ日時 2024-09-30 00:05:53
合計ジャッジ時間 20,650 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/python3

# 非再帰全方位木DP
# https://qiita.com/Kiri8128/items/a011c90d25911bdb3ed3 を改変
import sys
input = sys.stdin.readline
from collections import deque

# input
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

# topological sort
P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

# dp
dp = [(0, 1)] * N

for i in R[::-1]:
    for j in X[i]:
        dp[i] = (dp[i][0] + max(dp[j]), dp[i][1] + dp[j][0])

for i in R:
    for j in X[i]:
        dp_par = (dp[i][0] - max(dp[j][0], dp[j][1]), dp[i][1] - dp[j][0])
        dp[j] = (dp[j][0] + max(dp_par), dp[j][1] + dp_par[0])

print(min([a[1] for a in dp]))
0