結果
問題 | 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 // piusing 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;}