結果

問題 No.1752 Up-Down Tree
ユーザー gew1fw
提出日時 2025-06-12 17:10:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,297 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,696 KB
実行使用メモリ 113,280 KB
最終ジャッジ日時 2025-06-12 17:10:37
合計ジャッジ時間 5,355 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    if N == 1:
        print(1)
        return
    
    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b = map(int, sys.stdin.readline().split())
        edges[a].append(b)
        edges[b].append(a)
    
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    q = deque()
    q.append(1)
    parent[1] = -1  # Mark root
    
    while q:
        u = q.popleft()
        for v in edges[u]:
            if parent[v] == 0 and v != parent[u]:
                parent[v] = u
                children[u].append(v)
                q.append(v)
    
    size = [1] * (N + 1)
    stack = [(1, False)]
    
    while stack:
        u, visited = stack.pop()
        if visited:
            for v in children[u]:
                size[u] += size[v]
        else:
            stack.append((u, True))
            for v in reversed(children[u]):
                stack.append((v, False))
    
    root_children = children[1]
    sizes = []
    for c in root_children:
        sizes.append(size[c])
    
    sizes.sort(reverse=True)
    k = min(2, len(sizes))
    sum_two = sum(sizes[:k])
    print(1 + sum_two)

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