結果
問題 |
No.1098 LCAs
|
ユーザー |
|
提出日時 | 2020-06-26 23:44:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 278 ms / 2,000 ms |
コード長 | 895 bytes |
コンパイル時間 | 915 ms |
コンパイル使用メモリ | 85,104 KB |
最終ジャッジ日時 | 2025-01-11 12:20:16 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #define rep(i, j, n) for (i64 i = (j); i < (n); ++i) #define rrep(i, j, n) for (i64 i = (n)-1; i >= (j); --i) using namespace std; using i64 = int64_t; constexpr int INF = 1 << 30; // vの部分ぎの大きさを返す, ansには答えを入れる i64 dfs(int v, int p, vector<vector<int>> &g, vector<i64> &ans) { i64 res = 0; for (int nv : g[v]) { if (nv == p) continue; i64 tmp = dfs(nv, v, g, ans); ans[v] -= tmp * tmp; res += tmp; } ++res; ans[v] += res * res; return res; } int main() { int n, u, v; cin >> n; vector<vector<int>> g(n, vector<int>()); rep(i, 0, n - 1) { cin >> u >> v; --u, --v; g[u].push_back(v); g[v].push_back(u); } vector<i64> ans(n); dfs(0, 0, g, ans); rep(i, 0, n) cout << ans[i] << '\n'; return 0; }