제출 #386399

#제출 시각아이디문제언어결과실행 시간메모리
386399haojiandanMeetings 2 (JOI21_meetings2)C++14
100 / 100
705 ms38508 KiB
#include <bits/stdc++.h> using namespace std; template <typename T> void read(T &t) { t=0; char ch=getchar(); int f=1; while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f; } const int maxn=(2e5)+10; int n,S,head[maxn],to[maxn*2],tot,nxt[maxn*2]; void add(int x,int y) { tot++; nxt[tot]=head[x]; head[x]=tot; to[tot]=y; } int ans[maxn],N,vis[maxn]; void update(int &x,int y) { if (x<y) x=y; } int sz[maxn],mxsz[maxn],rt; void getrt(int u,int p) { sz[u]=1,mxsz[u]=0; for (int i=head[u],v;i;i=nxt[i]) { v=to[i]; if (v==p||vis[v]) continue; getrt(v,u); sz[u]+=sz[v]; mxsz[u]=max(mxsz[u],sz[v]); } //if (u%1000==0) printf("%d %d %d\n",u,sz[u],rt); mxsz[u]=max(mxsz[u],N-sz[u]); if (rt==-1||mxsz[u]<mxsz[rt]) rt=u; } int dep[maxn],st[maxn],st2[maxn],tot2,bel[maxn],now; vector<int> g[maxn]; void TRY(int u,int p,int flag) { N++; if (flag) { dep[u]=dep[p]+1; st[++tot]=u; sz[u]=1; bel[u]=now; } for (int i=head[u],v;i;i=nxt[i]) { v=to[i]; if (v==p||vis[v]) continue; TRY(v,u,flag); if (flag) sz[u]+=sz[v]; } if (flag) g[sz[u]].push_back(u); } bool cmp(int x,int y) { return sz[x]>sz[y]; } int mxdep[maxn]; pair<int,int> MX,MX2,tmp; vector<int> rem[maxn]; int deg[maxn]; void solve(int u,int NN) { vis[u]=1; tot=tot2=0; now=0; MX=MX2=make_pair(-1,-1); //printf("rt=%d %d\n",u,N); //if (N!=n) exit(0); int all=NN; tot2=0; for (int i=0;i<=all;i++) g[i].clear(); rem[u].resize(deg[u]+1); for (int i=head[u],v;i;i=nxt[i]) { v=to[i]; if (vis[v]) continue; N=0; tot=0; dep[u]=1; now++; TRY(v,u,1); rem[u][now]=N; for (int j=1;j<=tot;j++) update(ans[min(sz[st[j]],all-N)],dep[st[j]]); //printf("? %d %d\n",all,N); mxdep[now]=0; tmp=make_pair(0,now); if (tmp>MX) MX2=MX,MX=tmp; else MX2=max(MX2,tmp); } //for (int i=1;i<=n/2;i++) printf("%d ",ans[i]); puts(""); if (now>1) { for (int i=all,a;i>=0;i--) if (g[i].size()) { for (int v : g[i]) { a=bel[v]; // if (rt==2) printf("%d %d %d\n",v,dep[v],a); if (dep[v]>mxdep[a]) { tmp=make_pair(dep[v],a); if (MX==make_pair(mxdep[a],a)) MX=tmp; else if (MX2==make_pair(mxdep[a],a)) { if (tmp<MX) MX2=tmp; else MX2=MX,MX=tmp; } else if (tmp>MX) MX2=MX,MX=tmp; else MX2=max(MX2,tmp); mxdep[a]=dep[v]; if (MX.second!=a) update(ans[sz[v]],dep[v]+MX.first-1); else update(ans[sz[v]],dep[v]+MX2.first-1); //if (v==8) printf("?? %d %d %d %d\n",MX.first,MX.second,MX2.first,MX2.second); } } } } //for (int i=1;i<=n/2;i++) printf("%d ",ans[i]); puts(""); //exit(0); for (int i=head[u],v;i;i=nxt[i]) { v=to[i]; if (vis[v]) continue; N=rem[u][bel[v]]; rt=-1; getrt(v,u); solve(rt,N); } } int main() { //freopen("1.txt","r",stdin); read(n); int x,y; for (int i=1;i<n;i++) { read(x),read(y); add(x,y),add(y,x); deg[x]++,deg[y]++; } for (int i=1;i<=n;i++) ans[i]=1; N=n,rt=-1; getrt(1,0); //solve(8); //exit(0); solve(rt,n); for (int i=n;i>=1;i--) ans[i]=max(ans[i+1],ans[i]); for (int i=1;i<=n;i++) { if (i&1) puts("1"); else printf("%d\n",ans[i/2]); } return 0; } /* 0. Enough array size? Enough array size? Enough array size? Integer overflow? 1. Think TWICE, Code ONCE! Are there any counterexamples to your algo? 2. Be careful about the BOUNDARIES! N=1? P=1? Something about 0? 3. Do not make STUPID MISTAKES! Time complexity? Memory usage? Precision error? */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...