結果
問題 |
No.1418 Sum of Sum of Subtree Size
|
ユーザー |
![]() |
提出日時 | 2023-06-19 20:02:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 118 ms / 2,000 ms |
コード長 | 4,001 bytes |
コンパイル時間 | 2,232 ms |
コンパイル使用メモリ | 203,948 KB |
最終ジャッジ日時 | 2025-02-14 23:01:41 |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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; }