結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
![]() |
提出日時 | 2023-06-19 20:04:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 151 ms / 2,000 ms |
コード長 | 4,001 bytes |
コンパイル時間 | 2,304 ms |
コンパイル使用メモリ | 204,196 KB |
最終ジャッジ日時 | 2025-02-14 23:01:53 |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;template<typename S> struct Tree{vector<vector<S>> E, par0;vector<S> dist0;S N, log=0;Tree (const vector<vector<S>> &_E){N = _E.size(); E = _E;}//fromを根とする木の各頂点の深さを求めるvector<S> depth (S from) {vector<S> dist(N);_depth(from, -1, dist);return dist;}void _depth(S from, S p, vector<S> &dist) {for (auto to : E[from]){if (to == p) continue;dist[to] = dist[from]+1;_depth(to, from, dist);}}//木の二頂点(a, b)間の最短距離を求めるS dist(S a, S b){S c = lca(a, b);return dist0[a] + dist0[b]- 2*dist0[c];}//木の二頂点(a, b)のLCAを求めるS lca(S a, S b){if (par0.size() == 0){dist0 = depth(0);_doubling();}if (dist0[a] < dist0[b]) swap(a, b);for (S i=0; i<=log; i++){if ((dist0[a]-dist0[b]) & (1LL<<i)) a = par0[i][a];}if (a == b) return a;for (S i=log; i>=0; i--){if (par0[i][a] != par0[i][b]){a = par0[i][a];b = par0[i][b];}}return par0[0][a];}void _doubling(){S cnt = 1;while(cnt < N){cnt *= 2;log++;}par0.resize(log+1, vector<S>(N));_ancestor(0, -1);for (S i=1; i<=log; i++){for (S j=0; j<N; j++){if (par0[i-1][j] == -1) par0[i][j] = -1;else par0[i][j] = par0[i-1][par0[i-1][j]];}}}void _ancestor(S from, S p){par0[0][from] = p;for (auto to : E[from]){if (to == p) continue;_ancestor(to, from);}}//fromとgoalの最短経路上に含まれる点を全て求めるvector<S> shortest_path(S from, S goal) const{vector<S> path, pt;_shortest_path(from, goal, -1, pt, path);return path;}void _shortest_path(S from, S goal, S p, vector<S> &pt, vector<S> &path) const{pt.push_back(from);if (from == goal) path = pt;for (auto to : E[from]){if (to == p) continue;_shortest_path(to, goal, from, pt, path);}pt.pop_back();}//木の直径とその両端の点を求めるtuple<S, S, S> diameter() const{S s=0, t=0, mx=0;_diameter(s, -1, 0, mx, t);s=t; t=0; mx=0;_diameter(s, -1, 0, mx, t);return make_tuple(s, t, mx);}void _diameter(S from, S p, S d, S &mx, S &argmx) const{if (d > mx){argmx = from; mx = d;}for (auto to : E[from]){if (to == p) continue;_diameter(to, from, d+1, mx, argmx);}}//fromを根とする木の部分木のサイズを求めるvector<S> subtree_size(S from) const{vector<S> subtree(N);_subtree_size(from, -1, subtree);return subtree;}S _subtree_size(S from, S p, vector<S> &subtree) const{S cnt = 1;for (auto to : E[from]){if (to == p) continue;cnt += _subtree_size(to, from, subtree);}return subtree[from] = cnt;}};int main(){long long N, A, B, m, ans=0;cin >> N;vector<vector<long long>> E(N);ans = N*N;for (int i=0; i < N-1; i++){cin >> A >> B;A--; B--;E[A].push_back(B);E[B].push_back(A);}Tree tree(E);vector<ll> subtree = tree.subtree_size(0);for (int i=0; i<N; i++){for (auto x : E[i]){m = subtree[x];if (m > subtree[i]) m = N-subtree[i];ans += m * (N-m);}}cout << ans << endl;return 0;}