結果

問題 No.1928 Make a Binary Tree
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:51:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,323 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 849,516 KB
最終ジャッジ日時 2025-03-26 15:52:30
合計ジャッジ時間 26,629 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 32 MLE * 12 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    if N == 1:
        print(1)
        return

    # Build adjacency list
    adj = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        x, y = map(int, sys.stdin.readline().split())
        adj[x].append(y)
        adj[y].append(x)

    # Build parent and children structure using BFS
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    q = deque([1])
    parent[1] = -1  # mark root's parent as -1

    while q:
        u = q.popleft()
        for v in adj[u]:
            if parent[v] == 0 and v != parent[u]:
                parent[v] = u
                children[u].append(v)
                q.append(v)

    # Iterative post-order traversal
    stack = [(1, False)]
    dp = [0] * (N + 1)
    t1 = [0] * (N + 1)
    t2 = [0] * (N + 1)

    while stack:
        node, visited = stack.pop()
        if not visited:
            stack.append((node, True))
            # Push children in reverse order to process them in original order
            for child in reversed(children[node]):
                stack.append((child, False))
        else:
            max_a = max_b = 0
            # Collect t1 and t2 from all children
            for child in children[node]:
                current_t1 = t1[child]
                current_t2 = t2[child]
                # Update max_a and max_b with current_t1
                if current_t1 > max_a:
                    max_b = max_a
                    max_a = current_t1
                elif current_t1 > max_b:
                    max_b = current_t1
                # Update max_a and max_b with current_t2
                if current_t2 > max_a:
                    max_b = max_a
                    max_a = current_t2
                elif current_t2 > max_b:
                    max_b = current_t2

            a = max_a
            b = max_b
            dp[node] = 1 + a + b

            # Compute t1 and t2 for the current node
            if dp[node] > a:
                new_t1 = dp[node]
                new_t2 = a
            else:
                new_t1 = a
                new_t2 = max(b, dp[node])
            t1[node] = new_t1
            t2[node] = new_t2

    print(dp[1])

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