結果

問題 No.1928 Make a Binary Tree
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:53:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,129 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 157,952 KB
最終ジャッジ日時 2025-03-31 17:54:21
合計ジャッジ時間 18,315 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 9 RE * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

sys.setrecursionlimit(1 << 25)

n = int(sys.stdin.readline())

tree = [[] for _ in range(n+1)]
for _ in range(n-1):
    x, y = map(int, sys.stdin.readline().split())
    tree[x].append(y)
    tree[y].append(x)

parent = [0] * (n + 1)
children = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
q = deque([1])
visited[1] = True
parent[1] = 0  # root has no parent

while q:
    u = q.popleft()
    for v in tree[u]:
        if not visited[v] and v != parent[u]:
            parent[v] = u
            children[u].append(v)
            visited[v] = True
            q.append(v)

parent_uf = list(range(n + 1))
used = [0] * (n + 1)

def find(u):
    while True:
        if u == 0:
            return None  # root's parent is considered invalid
        if used[u] < 2:
            return u
        if parent_uf[u] == u:
            return None
        original_parent = parent_uf[u]
        parent_uf[u] = find(parent_uf[u])
        if parent_uf[u] is None:
            return None
        u = parent_uf[u]

post_order = []
stack = [(1, False)]
visited_p = [False] * (n + 1)

while stack:
    node, processed = stack.pop()
    if processed:
        post_order.append(node)
        continue
    if visited_p[node]:
        continue
    visited_p[node] = True
    stack.append((node, True))
    for child in reversed(children[node]):
        if not visited_p[child]:
            stack.append((child, False))

size = [0] * (n + 1)

for u in post_order:
    child_sizes = []
    for v in children[u]:
        child_sizes.append(size[v])
    child_sizes.sort(reverse=True)
    sum_children = sum(child_sizes[:2]) if len(child_sizes) >= 2 else (sum(child_sizes) if len(child_sizes) == 1 else 0)
    current = 1 + sum_children
    remaining = child_sizes[2:] if len(child_sizes) > 2 else []
    for vsize in remaining:
        w = find(parent[u])
        if w is not None:
            used[w] += 1
            current += vsize
            if used[w] >= 2:
                parent_uf[w] = parent[w] if parent[w] != 0 else w  # Update parent_uf for next find
    size[u] = current

print(size[1])
0