結果
問題 |
No.1098 LCAs
|
ユーザー |
![]() |
提出日時 | 2020-07-05 11:04:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 510 ms / 2,000 ms |
コード長 | 750 bytes |
コンパイル時間 | 1,867 ms |
コンパイル使用メモリ | 175,076 KB |
実行使用メモリ | 30,976 KB |
最終ジャッジ日時 | 2024-09-22 06:19:40 |
合計ジャッジ時間 | 10,657 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; int n; vector<vector<int>> hen; vector<int> dp; vector<ll> ans; int dfs(int v, int par) { if(dp[v])return dp[v]; ll sum = 1; ll res = 0; for(auto i : hen[v]) { if(i == par)continue; ll cur = dfs(i, v); sum += cur; res -= cur * cur; } res += (sum) * sum; ans[v] =res; return dp[v] = sum; } int main() { cin >> n; hen.resize(n), dp.resize(n), ans.resize(n); for(int i = 0; i < n - 1; i++) { int s, t; cin >> s >> t; s--, t--; hen[s].emplace_back(t); hen[t].emplace_back(s); } dfs(0, -1); for(int i = 0; i < n; i++) { cout << ans[i] << endl; } }