Submission #893663

#TimeUsernameProblemLanguageResultExecution timeMemory
8936638pete8Meetings 2 (JOI21_meetings2)C++17
100 / 100
393 ms32520 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<float.h> #include<limits.h> #include <cassert> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> //gcd(a,b) #include<bitset> using namespace std; #define ll long long #define f first #define endl "\n" #define s second #define pii pair<int,int> #define ppii pair<pii,int> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-loops") #define int long long using namespace std; const int mod=998244353,mxn=2e5+5,lg=30,inf=1e9,minf=-1e9,Mxn=100000; int n,sz[mxn+10],h[mxn+10],mx[mxn+10],ans[mxn+10]; pair<pii,pii> v[mxn+10]; vector<int>adj[mxn+10]; bitset<mxn+10>del; void getsz(int cur,int p){ sz[cur]=1; for(auto i:adj[cur]){ if(i==p||del[i])continue; getsz(i,cur); sz[cur]+=sz[i]; } } int getcen(int cur,int p,int need){ for(auto i:adj[cur])if(!del[i]&&i!=p&&sz[i]*2>need)return getcen(i,cur,need); return cur; } int cnt=0; void dfs(int cur,int p){ sz[cur]=1; for(auto i:adj[cur]){ if(i==p||del[i])continue; h[i]=h[cur]+1; dfs(i,cur); sz[cur]+=sz[i]; } mx[sz[cur]]=max(mx[sz[cur]],h[cur]); } void solve(int root){ if(del[root])assert(0); getsz(root,-1); int node=getcen(root,-1,sz[root]); h[node]=0; int sum=sz[root]; cnt=0; for(auto i:adj[node]){ if(del[i]){ cnt++; continue; } h[i]=1; dfs(i,node); mx[sz[i]+1]=minf; for(int j=sz[i];j>=0;j--){ mx[j]=max(mx[j],mx[j+1]); if(mx[j]==minf)continue; if(v[j].f.f==-1||v[j].f.f<mx[j]){ swap(v[j].f,v[j].s); v[j].f={mx[j],cnt}; } else if(v[j].s.f==-1||v[j].s.f<mx[j])v[j].s={mx[j],cnt}; } for(int j=0;j<=sz[i];j++)mx[j]=minf; cnt++; } int cmx=minf; for(int i=sum;i>=0;i--){ if(v[i].f.f==-1)continue; if(v[i].f.s<0)assert(0); if(v[i].s.f==-1&&sum-sz[adj[node][v[i].f.s]]>=i)cmx=max(cmx,v[i].f.f); else if(v[i].s.f!=-1) cmx=max(cmx,v[i].f.f+v[i].s.f); ans[i]=max(ans[i],cmx); v[i]={{-1,-1},{-1,-1}}; } del[node]=true; for(auto i:adj[node])if(!del[i])solve(i); } int32_t main(){ cin>>n; for(int i=0;i<n-1;i++){ int u,v;cin>>u>>v; adj[u].pb(v); adj[v].pb(u); } for(int i=0;i<=n;i++)v[i]={{-1,-1},{-1,-1}}; fill(mx,mx+mxn+5,minf); solve(1); for(int i=1;i<=n;i++){ if(i&1)cout<<1<<'\n'; else cout<<ans[i/2]+1<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...