結果
問題 |
No.1928 Make a Binary Tree
|
ユーザー |
|
提出日時 | 2022-05-07 02:20:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 255 ms / 3,000 ms |
コード長 | 651 bytes |
コンパイル時間 | 679 ms |
コンパイル使用メモリ | 77,968 KB |
実行使用メモリ | 47,088 KB |
最終ジャッジ日時 | 2024-07-06 06:07:19 |
合計ジャッジ時間 | 8,774 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
コンパイルメッセージ
main.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 36 | main() | ^~~~
ソースコード
#include<iostream> #include<set> #include<vector> using namespace std; int N; vector<int>G[2<<17]; multiset<int>ret; int dfs(int u,int p) { int ch=1; multiset<int>now; for(int v:G[u])if(v!=p) { int c=dfs(v,u); if(now.size()<ret.size())now.swap(ret); for(int d:ret)now.insert(d); now.insert(c); } if(!now.empty()) { auto it=now.end(); it--; ch+=*it; now.erase(it); if(!now.empty()) { auto it=now.end(); it--; ch+=*it; now.erase(it); } } ret.swap(now); return ch; } main() { cin>>N; for(int i=1;i<N;i++) { int u,v;cin>>u>>v;u--,v--; G[u].push_back(v); G[v].push_back(u); } cout<<dfs(0,-1)<<endl; }