結果
問題 |
No.1098 LCAs
|
ユーザー |
![]() |
提出日時 | 2021-03-18 22:54:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 542 ms / 2,000 ms |
コード長 | 756 bytes |
コンパイル時間 | 1,819 ms |
コンパイル使用メモリ | 169,424 KB |
実行使用メモリ | 36,300 KB |
最終ジャッジ日時 | 2024-11-17 05:00:10 |
合計ジャッジ時間 | 11,060 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; int N; long long dp[200005]; vector<int>ki[200005]; int dfs(int n,int p) { vector<int>tmp; for(auto x:ki[n]) { if(x != p) { tmp.push_back(dfs(x,n)); } } int ans = 1; for(int i = 0; i < tmp.size(); i++) { ans += tmp[i]; } long long ans2 = ans; for(int i = 0; i < tmp.size(); i++) { ans2 += (long long)(ans-tmp[i])*tmp[i]; } dp[n] = ans2; return ans; } int main() { cin >> N; for(int i = 0; i < N-1; i++) { int u,v; cin >> u >> v; u--;v--; ki[u].push_back(v); ki[v].push_back(u); } dfs(0,-1); for(int i = 0; i < N; i++) { cout << dp[i] << endl; } }