結果
問題 |
No.1418 Sum of Sum of Subtree Size
|
ユーザー |
![]() |
提出日時 | 2021-03-05 21:49:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 704 bytes |
コンパイル時間 | 1,922 ms |
コンパイル使用メモリ | 198,144 KB |
最終ジャッジ日時 | 2025-01-19 10:52:44 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; int n; long long res = 0; vector<vector<int>> g; vector<long long> cnt; long long solve(); long long dfs(int now = 0, int par = -1); int main() { cin >> n; g.resize(n); for (int i = 1; i < n; ++i) { int x, y; cin >> x >> y; g[--x].push_back(--y); g[y].push_back(x); } cout << solve() << endl; return 0; } long long solve() { cnt.assign(n, 1); dfs(); return res + (long long)n * n; } long long dfs(int now, int par) { for (auto to : g[now]) if (to != par) cnt[now] += dfs(to, now); res += cnt[now] * (n - cnt[now]); for (auto to : g[now]) if (to != par) res += cnt[to] * (n - cnt[to]); return cnt[now]; }