結果
問題 | No.1098 LCAs |
ユーザー |
![]() |
提出日時 | 2020-06-26 21:25:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,082 ms / 2,000 ms |
コード長 | 1,262 bytes |
コンパイル時間 | 3,007 ms |
コンパイル使用メモリ | 198,868 KB |
最終ジャッジ日時 | 2025-01-11 10:45:04 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define ALL(x) x.begin(),x.end()#define rep(i,n) for(int i=0;i<(n);i++)#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define INF 1000000000#define mod 1000000007using ll=long long;const ll LINF=1001002003004005006ll;int dx[]={1,0,-1,0};int dy[]={0,1,0,-1};// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}signed main(){cin.tie(0);ios::sync_with_stdio(0);int n;cin>>n;vector<vector<int>> g(n);rep(i,n-1){int u,v;cin>>u>>v;u--,v--;g[u].push_back(v);g[v].push_back(u);}vector<ll> sz(n,0);vector<int> par(n,-1);function<void(int,int)> dfs=[&](int pre,int now){ll res=1;par[now]=pre;for(auto to:g[now])if(to!=pre){dfs(now,to);res+=sz[to];}sz[now]=res;};dfs(-1,0);rep(i,n){ll res=0;for(auto to:g[i])if(to!=par[i]){res+=(sz[i]-sz[to])*sz[to];}res+=sz[i];cout<<res<<endl;}return 0;}