結果
問題 |
No.1418 Sum of Sum of Subtree Size
|
ユーザー |
![]() |
提出日時 | 2021-04-28 22:57:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 1,361 bytes |
コンパイル時間 | 545 ms |
コンパイル使用メモリ | 74,592 KB |
実行使用メモリ | 16,512 KB |
最終ジャッジ日時 | 2024-07-07 22:10:58 |
合計ジャッジ時間 | 3,658 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <iostream> #include <vector> using namespace std; using ll = long long int; using P = pair<int, int>; using graph = vector<vector<P>>; int dfs(graph &G, vector<bool> &isvisit, int cur, int parent){ if(isvisit[cur]) return 0; isvisit[cur] = true; int ans = 1; for(auto &p: G[cur]){ if(p.first == parent){ p.second = -1; continue; }else{ p.second = dfs(G, isvisit, p.first, cur); ans += p.second; } } return ans; } int main(){ int n; cin >> n; graph G(n); for(int i = 0; i < n-1; i++){ int a, b; cin >> a >> b; a--; b--; G[a].push_back(make_pair(b, -1)); G[b].push_back(make_pair(a, -1)); } //cerr << "input end" << endl; vector<bool> isvisit(n, false); dfs(G, isvisit, 0, -1); ll ans = 0; for(int i = 0; i < n; i++){ //for(auto &p: G[i]) cerr << "(" << p.first << ", " << p.second << ") "; //cerr << endl; ans += n; int childrenSum = 0; for(auto &p: G[i]){ if(p.second != -1) childrenSum += p.second; } for(auto &p: G[i]){ int xnum = p.second; if(xnum == -1) xnum = n-childrenSum-1; ans += (ll)(n-xnum) * xnum; } } cout << ans << endl; return 0; }