結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
|
提出日時 | 2021-03-06 17:10:06 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 623 ms / 2,000 ms |
コード長 | 442 bytes |
コンパイル時間 | 174 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 46,336 KB |
最終ジャッジ日時 | 2024-10-08 17:15:55 |
合計ジャッジ時間 | 10,867 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
import sys sys.setrecursionlimit(10 ** 6) n = int(input()) G = [[] for i in range(n)] for _ in range(n - 1): a, b = map(int, input().split()) G[a - 1].append(b - 1) G[b - 1].append(a - 1) ans = 0 def dfs(now, prev): global ans res = 1 for nex in G[now]: if nex == prev: continue tmp = dfs(nex, now) ans += tmp * (n - tmp) * 2 res += tmp ans += n return res dfs(0, -1) print(ans)