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