結果
問題 |
No.1098 LCAs
|
ユーザー |
![]() |
提出日時 | 2023-02-27 22:57:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 431 ms / 2,000 ms |
コード長 | 816 bytes |
コンパイル時間 | 394 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 124,408 KB |
最終ジャッジ日時 | 2024-09-15 04:36:08 |
合計ジャッジ時間 | 8,954 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
import sys readline = sys.stdin.readline def non_rec_dfs(s): stack = [] stack.append(s) par = [-1] * N sz = [1] * N dp = [0] * N while stack: u = stack.pop() if u >= 0: stack.append(~u) for v in G[u]: if v == par[u]: continue par[v] = u stack.append(v) else: u = ~u dp[u] += sz[u] ** 2 if par[u] != -1: sz[par[u]] += sz[u] dp[par[u]] -= sz[u] ** 2 return dp N = int(readline()) G = [[] for i in range(N)] for i in range(N - 1): u, v = map(int, readline().split()) u, v = u - 1, v - 1 G[u].append(v) G[v].append(u) dp = non_rec_dfs(0) for d in dp: print(d)