結果
問題 |
No.1418 Sum of Sum of Subtree Size
|
ユーザー |
👑 |
提出日時 | 2022-02-24 21:39:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 534 ms / 2,000 ms |
コード長 | 576 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 176,768 KB |
最終ジャッジ日時 | 2024-07-02 13:54:06 |
合計ジャッジ時間 | 9,756 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
import sys sys.setrecursionlimit(10 ** 9) import pypyjit pypyjit.set_param('max_unroll_recursion=-1') n = int(input()) edges = [[] for _ in range(n)] for _ in range(n - 1): u, v = map(int, input().split()) u -= 1 v -= 1 edges[u].append(v) edges[v].append(u) size = [1] * n ans = n * n def dfs(pos, bpos): global ans for npos in edges[pos]: if npos == bpos: continue dfs(npos, pos) size[pos] += size[npos] ans += size[npos] * (n - size[npos]) ans += size[pos] * (n - size[pos]) dfs(0, -1) print(ans)