結果
問題 | 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;}