結果
問題 | No.1098 LCAs |
ユーザー |
![]() |
提出日時 | 2024-03-06 01:21:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 532 ms / 2,000 ms |
コード長 | 1,315 bytes |
コンパイル時間 | 2,266 ms |
コンパイル使用メモリ | 204,560 KB |
最終ジャッジ日時 | 2025-02-20 01:10:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);ll N, A, B;cin >> N;vector<vector<ll>> E(N);for (int i=0; i < N-1; i++){cin >> A >> B;A--; B--;E[A].push_back(B);E[B].push_back(A);}//部分木のサイズvector<int> subt(N);auto subtree_size=[&](auto self, int from, int p)->void{subt[from]=1;for (auto to : E[from]){if (to == p) continue;self(self, to, from); subt[from] += subt[to];}};subtree_size(subtree_size, 0, -1);//各頂点の親const int LOG=1;vector par(LOG, vector<ll>(N, -1));auto ancestor=[&](auto self, int from, int p)->void{for (auto to : E[from]){if (to == p) continue;par[0][to] = from;self(self, to, from);}};ancestor(ancestor, 0, -1);for (int i=0; i<N; i++){ll S = 0, ans=0;vector<ll> v;for (auto x : E[i]){if (x != par[0][i]){v.push_back(subt[x]);S += subt[x];}}for (auto x : v) ans += x*(S-x);cout << ans + subt[i]*2-1 << endl;}return 0;}