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