結果

問題 No.1098 LCAs
ユーザー beet
提出日時 2020-06-26 21:35:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 267 ms / 2,000 ms
コード長 1,135 bytes
コンパイル時間 2,901 ms
コンパイル使用メモリ 197,604 KB
最終ジャッジ日時 2025-01-11 10:58:51
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';
template<typename F>
struct FixPoint : F{
FixPoint(F&& f):F(forward<F>(f)){}
template<typename... Args>
decltype(auto) operator()(Args&&... args) const{
return F::operator()(*this,forward<Args>(args)...);
}
};
template<typename F>
inline decltype(auto) MFP(F&& f){
return FixPoint<F>{forward<F>(f)};
}
//INSERT ABOVE HERE
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
Int n;
cin>>n;
vector<vector<Int>> G(n);
for(Int i=1;i<n;i++){
Int a,b;
cin>>a>>b;
a--;b--;
G[a].emplace_back(b);
G[b].emplace_back(a);
}
vector<Int> ans(n,0);
MFP([&](auto dfs,Int v,Int p)->Int{
Int sz=0;
for(Int u:G[v]){
if(u==p) continue;
Int sb=dfs(u,v);
ans[v]-=sb*sb;
sz+=sb;
}
ans[v]+=sz*sz;
ans[v]+=sz*2;
ans[v]+=1;
sz++;
return sz;
})(0,-1);
for(Int a:ans) cout<<a<<newl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0