結果

問題 No.1928 Make a Binary Tree
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:35:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,141 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 81,964 KB
実行使用メモリ 127,956 KB
最終ジャッジ日時 2025-04-15 22:37:15
合計ジャッジ時間 16,424 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        x, y = map(int, sys.stdin.readline().split())
        edges[x].append(y)
        edges[y].append(x)
    
    # Build the original tree and compute parent and depth
    parent = [0] * (N + 1)
    depth = [0] * (N + 1)
    visited = [False] * (N + 1)
    q = deque([1])
    visited[1] = True
    while q:
        u = q.popleft()
        for v in edges[u]:
            if not visited[v] and v != parent[u]:
                parent[v] = u
                depth[v] = depth[u] + 1
                visited[v] = True
                q.append(v)
    
    # Sort nodes by depth in decreasing order
    nodes = sorted(range(1, N+1), key=lambda x: -depth[x])
    
    # Initialize parent_available and child_count
    parent_available = [0] * (N + 1)
    for v in range(2, N+1):
        parent_available[v] = parent[v]
    parent_available[1] = None  # root's parent is None
    
    child_count = [0] * (N + 1)
    count = 1  # root is always present
    
    for v in nodes:
        if v == 1:
            continue  # skip root
        
        path = []
        current = parent[v]
        while True:
            if current is None:
                break
            path.append(current)
            if child_count[current] < 2:
                break
            current = parent_available[current]
        
        # Check if current is None and root can accommodate
        if current is None:
            if child_count[1] < 2:
                current = 1
        
        if current is not None and child_count[current] < 2:
            count += 1
            child_count[current] += 1
            if child_count[current] == 2:
                # Update parent_available for all nodes in path to current's parent_available
                new_parent = parent_available[current] if current != 1 else None
                for node in path:
                    parent_available[node] = new_parent
    
    print(count)

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