結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
|
提出日時 | 2021-03-05 22:34:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,128 bytes |
コンパイル時間 | 1,622 ms |
コンパイル使用メモリ | 170,012 KB |
実行使用メモリ | 17,664 KB |
最終ジャッジ日時 | 2024-10-07 03:14:39 |
合計ジャッジ時間 | 3,465 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
//#include <bits/stdc++.h>using namespace std;#define fi first#define se second#define all(x) x.begin(), x.end()#define lch (o << 1)#define rch (o << 1 | 1)typedef double db;typedef long long ll;typedef unsigned int ui;typedef pair<int, int> pint;typedef tuple<int, int, int> tint;const int N = 1e5 + 5;const int INF = 0x3f3f3f3f;const ll INF_LL = 0x3f3f3f3f3f3f3f3f;vector<int> a[N];int siz[N];ll sum[N];void getSize(int u, int pa) {siz[u] = 1;sum[u] = 0;for (auto v: a[u]) {if (v == pa) continue;getSize(v, u);siz[u] += siz[v];sum[u] += sum[v];}sum[u] += siz[u];}int n;ll ans = 0;void dfs(int u, int pa, int paSiz, ll paSum) {ans += (sum[u] - siz[u]) + paSum + n;for (auto v: a[u]) {if (v == pa) continue;int _paSiz = paSiz + siz[u] - siz[v];ll _paSum = paSum + (sum[u] - sum[v] - siz[u]) + _paSiz;dfs(v, u, _paSiz, _paSum);}}int main() {ios::sync_with_stdio(0);cin >> n;for (int i = 1; i < n; i++) {int u, v;cin >> u >> v;a[u].push_back(v);a[v].push_back(u);}getSize(1, 0);dfs(1, 0, 0, 0);cout << ans << endl;return 0;}