結果
問題 |
No.1098 LCAs
|
ユーザー |
|
提出日時 | 2020-06-26 22:03:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 178 ms / 2,000 ms |
コード長 | 818 bytes |
コンパイル時間 | 1,689 ms |
コンパイル使用メモリ | 171,492 KB |
実行使用メモリ | 30,244 KB |
最終ジャッジ日時 | 2024-07-04 21:11:16 |
合計ジャッジ時間 | 5,270 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr char newl = '\n'; ll dfs(int cur, int par, const vector< vector<int> >& g, vector<ll>& ans) { ll sum = 1; for (int nex : g[cur]) { if (nex == par) continue; ll cnt = dfs(nex, cur, g, ans); sum += cnt; ans[cur] -= cnt * cnt; } ans[cur] += sum * sum; return sum; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector< vector<int> > g(n); for (int i = 1; i < n; i++) { int v, w; cin >> v >> w; --v; --w; g[v].push_back(w); g[w].push_back(v); } vector<ll> ans(n, 0); dfs(0, -1, g, ans); for (int i = 0; i < n; i++) { cout << ans[i] << newl; } return 0; }