結果
問題 | No.1752 Up-Down Tree |
ユーザー |
![]() |
提出日時 | 2024-06-04 16:10:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 936 bytes |
コンパイル時間 | 1,843 ms |
コンパイル使用メモリ | 196,116 KB |
実行使用メモリ | 20,480 KB |
最終ジャッジ日時 | 2024-12-23 10:56:27 |
合計ジャッジ時間 | 4,028 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/priority_queue.hpp>#define heap __gnu_pbds::priority_queuetypedef long long ll;const int N=1e5+3;int n,ans;vector<int>ve[N];struct Nod{int x,op;};bool operator <(Nod A,Nod B){return A.x!=B.x?A.x<B.x:A.op<B.op;}heap<Nod>q[N];void Dfs(int x,int fa){if(ve[x].size()==1&&fa){q[x].push({1,0});return;}for(int y:ve[x])if(y!=fa)Dfs(y,x),q[x].join(q[y]);if(q[x].size()==1){Nod t=q[x].top();q[x].pop();ans=max(ans,t.x+1);q[x].push({1,0});q[x].push({t.x,1});return;}Nod t1=q[x].top();q[x].pop();Nod t2=q[x].top();q[x].pop();int v1=t1.x+t2.x,v2=t1.op|t2.op;if(t2.x==1&&!t2.op&&t1.op==1&&!q[x].size())v2=0;q[x].push({v1+1,v2});ans=max(ans,v1+1+v2);}int main(){cin>>n;if(n==1){cout<<1;return 0;}for(int i=1,x,y;i<n;i++)cin>>x>>y,ve[x].push_back(y),ve[y].push_back(x);Dfs(1,0);cout<<ans;return 0;}