結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
![]() |
提出日時 | 2021-03-05 22:17:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 1,579 bytes |
コンパイル時間 | 2,033 ms |
コンパイル使用メモリ | 199,036 KB |
最終ジャッジ日時 | 2025-01-19 11:18:29 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--) #define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++) #define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--) #define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++) #define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++) #define ALL(x) x.begin(), x.end() using ll = long long; using namespace std; ll dpf(vector<vector<int>> &tree, vector<ll> &dp, int now, int bf) { ll res = 1; for(auto nx : tree.at(now)) { if(nx == bf) continue; res += dpf(tree, dp, nx, now); } return dp.at(now) = res; } void dfs(vector<vector<int>> &tree, vector<ll> &dp, int now, int bf, ll &ans, ll &sum) { for(auto nx : tree.at(now)) { if(nx == bf) continue; ll nxdp = dp.at(now); ll nowdp = dp.at(now) - dp.at(nx); ll pnxdp = dp.at(nx); ll pnowdp = dp.at(now); ll d = (nxdp + nowdp) - (dp.at(now) + dp.at(nx)); sum += d; ans += sum; dp.at(now) = nowdp; dp.at(nx) = nxdp; dfs(tree, dp, nx, now, ans, sum); sum -= d; dp.at(now) = pnowdp; dp.at(nx) = pnxdp; } } int main() { int n; cin >> n; vector<vector<int>> tree(n, vector<int>()); rep(i, n-1){ int a, b; cin >> a >> b; a--; b--; tree.at(a).push_back(b); tree.at(b).push_back(a); } vector<ll> dp(n, 0); dpf(tree, dp, 0, -1); ll sum = accumulate(ALL(dp), 0LL); ll ans = sum; dfs(tree, dp, 0, -1, ans, sum); cout << ans << endl; return 0; }