結果

問題 No.1928 Make a Binary Tree
ユーザー gew1fw
提出日時 2025-06-12 14:43:53
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,285 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 848,944 KB
最終ジャッジ日時 2025-06-12 14:44:40
合計ジャッジ時間 10,839 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 MLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    edges = [[] for _ in range(N + 1)]
    index = 1
    for _ in range(N - 1):
        x = int(data[index])
        y = int(data[index + 1])
        edges[x].append(y)
        edges[y].append(x)
        index += 2

    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    stack = [1]
    parent[1] = -1  # Mark root's parent as -1

    while stack:
        u = stack.pop()
        for v in edges[u]:
            if parent[u] != v and parent[v] == 0:
                parent[v] = u
                children[u].append(v)
                stack.append(v)

    contribution = [0] * (N + 1)
    excess = [[] for _ in range(N + 1)]
    post_order_stack = [ (1, False) ]

    while post_order_stack:
        u, is_processed = post_order_stack.pop()
        if not is_processed:
            post_order_stack.append( (u, True) )
            for v in children[u]:
                post_order_stack.append( (v, False) )
        else:
            contributions = []
            for v in children[u]:
                contributions.append(contribution[v])
                contributions.extend(excess[v])
            
            a = 0
            b = 0
            for c in contributions:
                if c > a:
                    b = a
                    a = c
                elif c > b:
                    b = c
            
            sum_top = a + b
            contribution[u] = 1 + sum_top

            if a == b:
                count = 0
                new_excess = []
                for c in contributions:
                    if c == a and count < 2:
                        count += 1
                    else:
                        new_excess.append(c)
            else:
                count_a = 0
                count_b = 0
                new_excess = []
                for c in contributions:
                    if c == a and count_a < 1:
                        count_a += 1
                    elif c == b and count_b < 1:
                        count_b += 1
                    else:
                        new_excess.append(c)
            
            excess[u] = new_excess

    print(contribution[1])

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