結果

問題 No.1098 LCAs
ユーザー lam6er
提出日時 2025-03-20 21:08:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 703 ms / 2,000 ms
コード長 1,566 bytes
コンパイル時間 241 ms
コンパイル使用メモリ 81,780 KB
実行使用メモリ 136,840 KB
最終ジャッジ日時 2025-03-20 21:09:01
合計ジャッジ時間 10,298 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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):
        v, w = map(int, sys.stdin.readline().split())
        edges[v].append(w)
        edges[w].append(v)

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

    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 using iterative post-order DFS
    subtree_size = [0] * (n + 1)
    stack = [(1, False)]

    while stack:
        node, visited = stack.pop()
        if not visited:
            stack.append((node, True))
            # Push children in reverse order to process them in the original order
            for child in reversed(children[node]):
                stack.append((child, False))
        else:
            size = 1
            for child in children[node]:
                size += subtree_size[child]
            subtree_size[node] = size

    # Compute answers
    for k in range(1, n + 1):
        sum_sq = 0
        for child in children[k]:
            sum_sq += subtree_size[child] ** 2
        ans = subtree_size[k] ** 2 - sum_sq
        print(ans)

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