結果
問題 |
No.1098 LCAs
|
ユーザー |
|
提出日時 | 2020-06-27 06:31:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,944 ms / 2,000 ms |
コード長 | 548 bytes |
コンパイル時間 | 220 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 433,112 KB |
最終ジャッジ日時 | 2024-07-05 08:48:34 |
合計ジャッジ時間 | 11,969 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
import sys input = sys.stdin.readline sys.setrecursionlimit(2*10**5+100) def dfs(v, pv): l = [] for nv in G[v]: if nv==pv: continue l.append(dfs(nv, v)) s = sum(l) for li in l: ans[v] += li*(s-li) for li in l: ans[v] += 2*li return s+1 N = int(input()) G = [[] for _ in range(N)] for _ in range(N-1): v, w = map(int, input().split()) G[v-1].append(w-1) G[w-1].append(v-1) ans = [1]*N dfs(0, -1) for ans_i in ans: print(ans_i)