제출 #976584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976584		happy_node	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	575 ms	32084 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;

const int MX=2e5+5;
int N;
vector<int> adj[MX];

bool used[MX];
int sz[MX]; 

int f[MX];
vector<pair<int,int>> mxs[MX];

int getSize(int v, int p) {
	sz[v]=1;
	for(auto u:adj[v]) {
		if(u==p || used[u]) continue;
		sz[v]+=getSize(u,v);
	}
	return sz[v];
}

int getCen(int v, int p, int s) {
	for(auto u:adj[v]) {
		if(u==p || used[u]) continue;
		if(2*sz[u]>s) return getCen(u,v,s);
	}
	return v;
}

int head=0,s=0;
int ans[MX];

void dfs(int v, int p, int dep) {
	f[sz[v]]=max(f[sz[v]],dep);

	int i=min(sz[v],s-sz[head]);
	ans[2*i]=max(ans[2*i],dep+1);

	for(auto u:adj[v]) {
		if(u==p || used[u]) continue;
		dfs(u,v,dep+1);
	}
}

void cdc(int v) {
	s=getSize(v,v);
	int cen=getCen(v,v,s);
	used[cen]=true;
	getSize(cen,cen);

	for(auto u:adj[cen]) {
		if(!used[u]) {
			head=u;
			dfs(u,cen,1);

			for(int i=1;i<=sz[u];i++) {
				mxs[i].push_back({f[i],u});
				sort(mxs[i].rbegin(),mxs[i].rend());
				while(mxs[i].size()>2) mxs[i].pop_back();
				f[i]=0;
			}
		}
	}

	vector<pair<int,int>> vv;

	for(int i=s;i>=1;i--) {
		vector<pair<int,int>> nv;
		for(auto [fi,u]:mxs[i]) {
			vv.push_back({fi,u});
		}
		sort(vv.rbegin(),vv.rend());
		for(auto [fi,u]:vv) {
			if(nv.empty()) {
				nv.push_back({fi,u});
				continue;
			}
			if(nv.size()==1) {
				if(nv.back().second!=u) nv.push_back({fi,u});
				continue;
			}
			break;
		}
		swap(vv,nv);
		if(vv.size()>1) {
			ans[2*i]=max(ans[2*i],vv[0].first+vv[1].first+1);
		}
	}

	for(int i=1;i<=sz[cen];i++) {
		mxs[i].clear();
	}

	for(auto u:adj[cen]) {
		if(!used[u]) {
			cdc(u);
		}
	}
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N;
	for(int i=1;i<N;i++) {
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cdc(1);

	ans[N+1]=1;
	for(int i=N;i>=1;i--) 
		ans[i]=max(ans[i],ans[i+1]);

	for(int i=1;i<=N;i++) {
		if(i&1) {
			cout<<1<<'\n';
		} else {
			cout<<ans[i]<<'\n';
		}
	}
}

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