結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
![]() |
提出日時 | 2021-03-13 03:21:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 1,650 bytes |
コンパイル時間 | 814 ms |
コンパイル使用メモリ | 96,272 KB |
実行使用メモリ | 12,020 KB |
最終ジャッジ日時 | 2024-10-14 15:35:39 |
合計ジャッジ時間 | 4,124 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
/* -*- coding: utf-8 -*-** 1418.cc: No.1418 Sum of Sum of Subtree Size - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 100000;/* typedef */typedef long long ll;typedef vector<int> vi;/* global variables */vi nbrs[MAX_N];int ps[MAX_N], cis[MAX_N];int szs[MAX_N];ll ss[MAX_N], rss[MAX_N];/* subroutines *//* main */int main() {int n;scanf("%d", &n);for (int i = 1; i < n; i++) {int u, v;scanf("%d%d", &u, &v);u--, v--;nbrs[u].push_back(v);nbrs[v].push_back(u);}ps[0] = -1;for (int u = 0; u >= 0;) {vi &nbru = nbrs[u];if (cis[u] < nbru.size() && nbru[cis[u]] == ps[u]) cis[u]++;if (cis[u] < nbru.size()) {int v = nbru[cis[u]++];ps[v] = u;u = v;}else {szs[u]++;ss[u] += szs[u];if (ps[u] >= 0) {szs[ps[u]] += szs[u];ss[ps[u]] += ss[u];}u = ps[u];}}rss[0] = ss[0];ll sum = rss[0];memset(cis, 0, sizeof(cis));for (int u = 0; u >= 0;) {vi &nbru = nbrs[u];if (cis[u] < nbru.size() && nbru[cis[u]] == ps[u]) cis[u]++;if (cis[u] < nbru.size()) {int v = nbru[cis[u]++];rss[v] = rss[u] + n - szs[v] * 2;sum += rss[v];u = v;}else {u = ps[u];}}printf("%lld\n", sum);return 0;}