結果
問題 | No.1098 LCAs |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:39:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 516 ms / 2,000 ms |
コード長 | 862 bytes |
コンパイル時間 | 3,983 ms |
コンパイル使用メモリ | 201,176 KB |
最終ジャッジ日時 | 2025-01-11 11:54:42 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(int i = 0; i < (n);i++)#define sz(x) int(x.size())typedef long long ll;typedef long double ld;typedef pair<int,int> P;typedef pair<ll, int> PL;constexpr ll INF = (1LL << 60);int main() {int n;cin >> n;vector<vector<int>> g(n);rep(i, n - 1) {int u, v;cin >> u >> v;u--; v--;g[u].emplace_back(v);g[v].emplace_back(u);}vector<ll> dp(n, 0);vector<ll> sum(n, 0);auto dfs = [&](auto& f, int u = 0, int p = -1)->void{sum[u] = 1;for (auto v : g[u]) {if (v == p) continue;f(f, v, u);sum[u] += sum[v];dp[u] -= sum[v] * (sum[v] - 1) / 2;}dp[u] += sum[u] * (sum[u] - 1) / 2;dp[u] *= 2;dp[u]++;};dfs(dfs);for (int i = 0; i < n; i++) {cout << dp[i] << endl;}return 0;}