結果
問題 |
No.1098 LCAs
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()