結果
問題 | No.1752 Up-Down Tree |
ユーザー |
![]() |
提出日時 | 2024-06-04 15:41:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,764 bytes |
コンパイル時間 | 2,082 ms |
コンパイル使用メモリ | 178,064 KB |
実行使用メモリ | 28,288 KB |
最終ジャッジ日時 | 2024-12-23 10:56:14 |
合計ジャッジ時間 | 4,236 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 RE * 1 |
ソースコード
# include <bits/stdc++.h> # define fir first # define sec second # define mp std::make_pair const int N=100010,INF=0x3f3f3f3f; inline int read(void){ int res,f=1; char c; while((c=getchar())<'0'||c>'9') if(c=='-') f=-1; res=c-48; while((c=getchar())>='0'&&c<='9') res=res*10+c-48; return res*f; } int n; int f[N]; std::vector <int> G[N]; void init(int x,int fa){ f[x]=fa; for(auto y:G[x]) if(y!=fa) init(y,x); return; } std::multiset <std::pair <int,int> > S[N]; int ans; // int fmax[N]; // do not consider last step up. void solve(int x){ if(f[x]&&G[x].size()==1){ S[x].insert(mp(1,0)); return; } int id=0; for(auto y:G[x]){ if(y==f[x]) continue; solve(y); if(S[id].size()<S[y].size()) id=y; // for(auto v:S[y]) S[x].insert(v); } S[x].swap(S[id]); for(auto y:G[x]){ if(y==f[x]||y==id) continue; for(auto v:S[y]) S[x].insert(v); } ans=std::max(ans,(*S[x].rbegin()).fir+(*S[x].rbegin()).sec); if(S[x].size()!=1){ auto it=S[x].end(); auto u=--it; auto v=--it; int w=(*u).fir+(*v).fir,k=(*u).sec|(*v).sec; // printf("u = %d %d v = %d %d\n",(*u).fir,(*u).sec,(*v).fir,(*v).sec); if(*v==mp(1,0)&&(*u).sec==1){ if(it==S[x].begin()) k=0; } S[x].erase(u),S[x].erase(v),S[x].insert(mp(w+1,k)); ans=std::max(ans,w+1+k); }else{ auto it=*S[x].begin(); S[x].clear(); S[x].insert(mp(it.fir,1)),ans=std::max(it.fir+1,ans); S[x].insert(mp(1,0)); } // printf("at %d:",x); // for(auto v:S[x]) printf("(%d,%d) ",v.fir,v.sec); // puts(""); return; } int main(void){ // freopen("bird.in","r",stdin); // freopen("bird.out","w",stdout); n=read(); for(int i=2,u,v;i<=n;++i) u=read(),v=read(),G[u].push_back(v),G[v].push_back(u); init(1,0); solve(1); printf("%d",ans); return 0; }