제출 #386399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386399		haojiandan	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	705 ms	38508 KiB

meetings2

#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?
*/

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80