結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
![]() |
提出日時 | 2021-03-05 23:12:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 1,057 bytes |
コンパイル時間 | 1,938 ms |
コンパイル使用メモリ | 197,364 KB |
最終ジャッジ日時 | 2025-01-19 11:57:26 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; using graph = vector<vector<int>>; void dfs(const graph &to, vector<int64_t> &child, vector<int64_t> &par, int v, int p) { par.at(v) = p; for (auto &&i : to.at(v)) { if (i == p) continue; dfs(to, child, par, i, v); child.at(v) += child.at(i); } child.at(v)++; } int main(int argc, char const *argv[]) { int64_t n; cin >> n; graph to(n); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; to.at(a).push_back(b); to.at(b).push_back(a); } vector<int64_t> child(n), par(n); dfs(to, child, par, 0, -1); assert(child.at(0) == n); int64_t ans = n * n * n; for (int i = 0; i < n; i++) { for (auto &&c : to.at(i)) { if (c == par.at(i)) continue; ans -= child.at(c) * child.at(c); } ans -= (n - child.at(i)) * (n - child.at(i)); } cout << ans << endl; return 0; }