結果
問題 |
No.1098 LCAs
|
ユーザー |
|
提出日時 | 2020-07-24 15:59:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 624 ms / 2,000 ms |
コード長 | 744 bytes |
コンパイル時間 | 812 ms |
コンパイル使用メモリ | 71,936 KB |
実行使用メモリ | 43,264 KB |
最終ジャッジ日時 | 2024-06-25 07:08:55 |
合計ジャッジ時間 | 9,649 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<iostream> #include<vector> using namespace std; vector<int> v[200000], child, way[200000]; void dfs(int p, int x){ child[x] = 1; for(int c : v[x]){ if(c == p) continue; dfs(x, c); way[x].push_back(c); child[x] += child[c]; } } typedef long long ll; int main(){ int n; cin >> n; child.resize(n, 0); for(int i = 0; i < n-1; i++){ int a, b; cin >> a >> b; a--, b--; v[a].push_back(b); v[b].push_back(a); } dfs(-1, 0); for(int i = 0; i < n; i++){ ll ans = 2*child[i]-1; for(int c : way[i]){ ans += (ll)child[c]*(child[i]-1-child[c]); } cout << ans << endl; } return 0; }