結果

問題 No.1752 Up-Down Tree
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:00:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,461 bytes
コンパイル時間 538 ms
コンパイル使用メモリ 81,924 KB
実行使用メモリ 130,772 KB
最終ジャッジ日時 2025-04-09 21:01:41
合計ジャッジ時間 7,525 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from sys import stdin
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    n = int(stdin.readline())
    edges = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a, b = map(int, stdin.readline().split())
        edges[a].append(b)
        edges[b].append(a)

    # Build parent and children structure with BFS
    parent = [0]*(n+1)
    children = [[] for _ in range(n+1)]
    q = deque()
    q.append(1)
    parent[1] = -1  # 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)

    # Compute subtree sizes via post-order traversal
    subtree = [1]*(n+1)
    stack = [(1, False)]
    while stack:
        node, visited = stack.pop()
        if visited:
            size = 1
            for child in children[node]:
                size += subtree[child]
            subtree[node] = size
        else:
            stack.append( (node, True) )
            for child in children[node][::-1]:
                stack.append( (child, False) )

    # Precompute for each node a and child c, max_other_child_size
    # For each a, we'll store a dictionary: child -> max_other_child_size
    max_other_child = [{} for _ in range(n+1)]
    for a in range(1, n+1):
        if not children[a]:
            continue
        max_size = -1
        second_max = -1
        best_child = -1
        for c in children[a]:
            s = subtree[c]
            if s > max_size:
                second_max = max_size
                max_size = s
                best_child = c
            elif s > second_max:
                second_max = s
        for c in children[a]:
            if c == best_child:
                # When excluding best_child, the max is second_max
                current_max = second_max if second_max != -1 else 0
            else:
                current_max = max_size
            max_other_child[a][c] = current_max

    # For each node, compute the sum of max_other_child from ancestors
    # Also compute depth
    sum_max = [0]*(n+1)
    depth = [0]*(n+1)
    # We'll compute via BFS from root to leaves, tracking path
    # Each node's sum is parent_sum + max_other_child of parent
    # depth is parent_depth + 1

    # Process each node by their path from root
    # Initialize
    sum_max[1] = 0
    depth[1] = 1

    # Queue will process nodes level by level
    q = deque()
    q.append( (1, 0, 1) )  # (node, sum_val, depth)
    while q:
        u, s_val, d = q.popleft()
        for v in children[u]:
            # sum_max[v] = sum_max[u] + max_other_child[u].get(v,0)
            # (since u's parent's path is preserved)
            # So when moving to v, the max_other_child for u's parent's path
            # plus the max_other_child[u][v]
            current_parent = u
            # if current_parent is 1, then ancestor sums...
            # The sum for v is sum_max[u] + max_other_child for u where child is v
            sum_v = sum_max[u] + max_other_child[current_parent].get(v,0)
            depth_v = d + 1
            sum_max[v] = sum_v
            depth[v] = depth_v
            q.append( (v, sum_v, depth_v) )

    max_total = 0
    for u in range(1, n+1):
        total = depth[u] + sum_max[u]
        if total > max_total:
            max_total = total
    print(max_total)

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