結果
問題 | No.1098 LCAs |
ユーザー |
|
提出日時 | 2021-12-25 10:59:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,812 ms / 2,000 ms |
コード長 | 941 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 82,264 KB |
実行使用メモリ | 459,156 KB |
最終ジャッジ日時 | 2024-09-21 12:53:18 |
合計ジャッジ時間 | 11,352 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N = int(input())G = [[] for _ in range(N+1)]for _ in range(N-1):u,v = map(int,input().split())G[u].append(v)G[v].append(u)memo = [0] * (N+1)import syssys.setrecursionlimit(10 ** 6)def calc(now = 1,parent = 0):if now != 1 and len(G[now]) == 1:memo[now] = 1return 1ans = 1for v in G[now]:if v != parent:ans += calc(v,now)memo[now] = ansreturn anscalc()for k in range(1,N+1):ans = memo[k] * 2 - 1if k == 1:if len(G[k]) == 1:print(ans)continueelse:for u in G[k]:ans += memo[u] * (memo[k] - memo[u] - 1)print(ans)else:if len(G[k]) <= 2:print(ans)continueelse:for u in G[k]:if memo[u] < memo[k]:ans += memo[u] * (memo[k] - memo[u] - 1)print(ans)