結果
問題 |
No.1098 LCAs
|
ユーザー |
![]() |
提出日時 | 2020-06-27 13:45:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 547 ms / 2,000 ms |
コード長 | 1,238 bytes |
コンパイル時間 | 2,165 ms |
コンパイル使用メモリ | 197,756 KB |
最終ジャッジ日時 | 2025-01-11 12:48:49 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> #define M_PI 3.14159265358979323846 // pi using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<ll> VI; typedef pair<ll, ll> P; typedef tuple<ll, ll, ll> t3; typedef tuple<ll, ll, ll, ll> t4; typedef tuple<ll, ll, ll, ll, ll> t5; #define rep(a,n) for(ll a = 0;a < n;a++) #define repi(a,b,n) for(ll a = b;a < n;a++) using namespace std; static const ll INF = 1e15; const ll mod = 1000000007; vector<vector<int>> g; vector<int> dp; vector<vector<int>> children; int dfs(int current, int parent) { if (dp[current]) { return dp[current]; } int sum = 1; for (int i = 0; i < g[current].size(); i++) { if (g[current][i] != parent) { auto d = dfs(g[current][i], current); sum += d; children[current].push_back(d); } } dp[current] = sum; return sum; } int main() { int n; cin >> n; g.resize(n); dp.resize(n); children.resize(n); rep(i, n - 1) { int v, w; cin >> v >> w; v--; w--; g[v].push_back(w); g[w].push_back(v); } dfs(0, -1); rep(i, n) { ll total = 0; ll cSum = 0; for (auto child : children[i]){ total += child * cSum * 2; cSum += child; } total += cSum * 2 + 1; cout << total << endl; } return 0; }