제출 #957708

#제출 시각아이디문제언어결과실행 시간메모리
957708LCJLYMeetings 2 (JOI21_meetings2)C++14
0 / 100
6 ms38236 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define show(x,y) cout << y << " " << #x << endl; #define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl; #define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl; #define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl; typedef pair<long long,int>pii; typedef pair<pii,pii>pi2; mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); vector<int>adj[200005]; int sz[200005]; int two[22][200005]; int d[200005]; int n; void dfs(int index, int par){ sz[index]=1; for(int x=0;x<20;x++){ two[x+1][index]=two[x][two[x][index]]; } for(auto it:adj[index]){ if(it==par) continue; two[0][it]=index; d[it]=d[index]+1; dfs(it,index); sz[index]+=sz[it]; } } int cent(int index, int par){ for(auto it:adj[index]){ if(it!=par&&sz[it]>n/2){ return cent(it,index); } } return index; } int lca(int a, int b){ if(d[a]>d[b]) swap(a,b); int diff=d[b]-d[a]; for(int x=0;x<20;x++){ if(diff&(1<<x)){ b=two[x][b]; } } if(a==b) return a; for(int x=19;x>=0;x--){ if(two[x][a]!=two[x][b]){ a=two[x][a]; b=two[x][b]; } } return two[0][a]; } int f(int a, int b){ int hold=lca(a,b); return d[a]+d[b]-2*d[hold]; } void solve(){ cin >> n; int temp,temp2; for(int x=0;x<n-1;x++){ cin >> temp >> temp2; adj[temp].push_back(temp2); adj[temp2].push_back(temp); } dfs(1,-1); int rt=cent(1,-1); dfs(rt,-1); //show(check,1); int ans[n+5]; memset(ans,0,sizeof(ans)); pii cur={rt,rt}; int dist=0; vector<pii>v; for(int x=1;x<=n;x++){ v.push_back({sz[x],x}); } sort(v.begin(),v.end()); reverse(v.begin(),v.end()); for(int x=0;x<n;x++){ int index=v[x].second; int hold=f(cur.first,index); int hold2=f(cur.second,index); pii temp={cur.second,index}; if(hold>dist){ cur={cur.first,index}; dist=hold; } if(hold2>dist){ dist=hold2; cur=temp; } ans[sz[index]]=dist; } for(int x=n;x>=0;x--){ ans[x]=max(ans[x+1],ans[x]); } for(int x=1;x<=n;x++){ if(x%2){ cout << 1 << "\n"; } else{ cout << ans[x/2]+1 << "\n"; } } } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...