結果
問題 | No.1098 LCAs |
ユーザー |
![]() |
提出日時 | 2020-06-27 14:46:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 408 ms / 2,000 ms |
コード長 | 1,919 bytes |
コンパイル時間 | 1,752 ms |
コンパイル使用メモリ | 172,372 KB |
実行使用メモリ | 30,336 KB |
最終ジャッジ日時 | 2024-07-05 09:10:59 |
合計ジャッジ時間 | 7,953 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include "bits/stdc++.h"#include<vector>#include<iostream>#include<queue>#include<algorithm>#include<map>#include<set>#include<iomanip>#include<assert.h>#include<unordered_map>#include<unordered_set>#include<string>#include<stack>#include<complex>#include<memory>#pragma warning(disable:4996)using namespace std;using ld = long double;template<class T>using Table = vector<vector<T>>;const ld eps=1e-9;using Graph=vector<vector<int>>;using ll=long long;#define WHATS(var)cout<<__LINE__<<' '<<#var<<"="<<var<<endl;template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){os << "( " << v.first << ", " << v.second << ")"; return os;}template<class T> ostream& operator <<(ostream &os, const vector<T> &v){for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;}template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;}template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;}template<class T> ostream& operator <<(ostream &os, const set<T> &v){int i=0;for(auto it:v){if(i > 0){os << ' ';}os << it;i++;}return os;}ll dfs(int now,int from,const Graph&g,vector<ll>&anss){ll sum=0;for(auto e:g[now]){if(e!=from){ll kk=dfs(e,now,g,anss);anss[now]-=kk*kk;sum+=kk;}}sum++;anss[now]+=ll(sum)*sum;return sum;}int main() {ios::sync_with_stdio(false);cin.tie();int N;cin>>N;Graph g(N);for(int i=0;i<N-1;++i){int u,v;cin>>u>>v;u--;v--;g[u].push_back(v);g[v].push_back(u);}vector<ll>anss(N);dfs(0,-1,g,anss);for(auto a:anss)cout<<a<<endl;return 0;}