結果

問題 No.763 Noelちゃんと木遊び
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:53:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 269 ms / 2,000 ms
コード長 1,727 bytes
コンパイル時間 257 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 109,644 KB
最終ジャッジ日時 2025-03-22 10:44:30
合計ジャッジ時間 5,830 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    n = int(sys.stdin.readline())
    if n == 0:
        print(0)
        return
    
    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        adj[v].append(u)
    
    # Build children structure using BFS
    children = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    q = deque()
    root = 1
    visited[root] = True
    q.append((root, 0))  # (node, parent)
    
    while q:
        u, parent = q.popleft()
        for v in adj[u]:
            if v != parent and not visited[v]:
                visited[v] = True
                children[u].append(v)
                q.append((v, u))
    
    # Iterative post-order traversal to compute DP
    dp0 = [0] * (n + 1)  # dp0[u] = maximum independent set when u is not included
    dp1 = [0] * (n + 1)  # dp1[u] = maximum independent set when u is included
    stack = [(root, False)]
    
    while stack:
        node, processed = stack.pop()
        if not processed:
            stack.append((node, True))
            # Push children in reverse order to process left to right
            for child in reversed(children[node]):
                stack.append((child, False))
        else:
            # Compute dp1[node] and dp0[node]
            dp1[node] = 1  # Include current node
            for child in children[node]:
                dp1[node] += dp0[child]
            
            dp0[node] = 0  # Do not include current node
            for child in children[node]:
                dp0[node] += max(dp0[child], dp1[child])
    
    print(max(dp0[root], dp1[root]))

if __name__ == "__main__":
    main()
0