結果

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

ソースコード

diff # 

import sys
from sys import stdin
sys.setrecursionlimit(1 << 25)

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    edges = [[] for _ in range(n+1)]
    ptr = 1
    for _ in range(n-1):
        u = int(input[ptr])
        v = int(input[ptr+1])
        ptr += 2
        edges[u].append(v)
        edges[v].append(u)
    
    # 木の構築と根の選択（根を1とする）
    # DPのためのグラフを構築する（親子関係を記録）
    parent = [0]*(n+1)
    children = [[] for _ in range(n+1)]
    stack = [1]
    visited = [False]*(n+1)
    visited[1] = True
    while stack:
        u = stack.pop()
        for v in edges[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                children[u].append(v)
                stack.append(v)
    
    # DPを実行
    selected = [0]*(n+1)
    not_selected = [0]*(n+1)
    stack = []
    post_order = []
    stack.append((1, False))
    while stack:
        u, processed = stack.pop()
        if processed:
            post_order.append(u)
            continue
        stack.append((u, True))
        for v in children[u]:
            stack.append((v, False))
    
    for u in post_order:
        # selected[u] = 1 + sum not_selected of children
        s = 1
        for v in children[u]:
            s += not_selected[v]
        selected[u] = s
        
        # not_selected[u] = sum max(selected[v], not_selected[v]) for children
        ns = 0
        for v in children[u]:
            ns += max(selected[v], not_selected[v])
        not_selected[u] = ns
    
    print(max(selected[1], not_selected[1]))
    
if __name__ == "__main__":
    main()
0