結果
問題 |
No.1098 LCAs
|
ユーザー |
|
提出日時 | 2022-07-25 23:50:01 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 616 bytes |
コンパイル時間 | 136 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 99,328 KB |
最終ジャッジ日時 | 2024-12-20 18:45:43 |
合計ジャッジ時間 | 26,156 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 TLE * 3 |
ソースコード
import sys sys.setrecursionlimit(10**7) N = int(input()) lsg = [[] for i in range(N)] for i in range(N-1): v,w = map(int,input().split()) v -= 1 w -= 1 lsg[v].append(w) lsg[w].append(v) dp = [0]*(N) dp2 = [[1] for i in range(N)] def dfs(k,p): cnt = 1 for j in lsg[k]: if j == p: continue c = dfs(j,k) dp2[k].append(c) cnt += c dp[k] = cnt return cnt dfs(0,-1) for i in range(N): l = dp2[i] if len(l) == 1: print(1) continue sm = sum(l) ans = 1 for j in l: ans += j*(sm-j) print(ans)