Submission #523227

#	Time	Username	Problem	Language	Result	Execution time	Memory
523227		amunduzbaev	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	9 ms	14412 KiB

meetings2

#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 2e5 + 5;
vector<int> edges[N];
set<ar<int, 2>> ss[N];
int sub[N], d[N], par[N][20];

void dfs(int u, int p = -1){
	sub[u] = 1;
	par[u][0] = p;
	for(int j=1;j<20;j++) par[u][j] = par[par[u][j-1]][j-1];
	for(auto x : edges[u]){
		if(x == p) continue;
		d[x] = d[u] + 1;
		dfs(x, u);
		sub[u] += sub[x];
	}
}

int rr[N<<1];

void dfs1(int u, int p = -1){
	//~ ss[u].insert({sub[u], d[u]});
	
	auto add = [&](ar<int, 2> x){
		auto it = ss[u].lower_bound({x[0] + 1, -1});
		if(it != ss[u].end()){
			if((*it)[1] >= x[1]) return;;
		}
		
		vector<ar<int, 2>> del;
		while(it != ss[u].begin()){
			it--;
			if((*it)[1] > x[1]) break;
			del.push_back(*it);
		}
		
		for(auto x : del) ss[u].erase(x);
		ss[u].insert(x);
	};
	
	int x = u;
	for(int j=19;~j;j--){
		if(sub[1] - sub[par[x][j]] >= sub[u]) x = par[x][j];
	} x = par[x][0];
	
	rr[sub[u] * 2] = max(rr[sub[u] * 2], d[u] - d[x] + 1);
	
	for(auto v : edges[u]){
		if(v == p) continue;
		dfs1(v, u);
		//~ if((int)ss[u].size() < (int)ss[v].size()) swap(ss[u], ss[v]);
		for(auto x : ss[v]){
			auto it = ss[u].lower_bound({x[0], -1});
			if(it != ss[u].end()){
				//~ cout<<x[0]<<" "<<x[1]<<" "<<(*it)[1]<<" "<<d[u]<<endl;
				rr[x[0] * 2] = max(rr[x[0] * 2], (*it)[1] + x[1] - d[u] * 2 + 1);
			}
		}
		
		for(auto x : ss[v]){
			add(x);
		} ss[v].clear();
	}
	
	reverse(edges[u].begin(), edges[u].end());
	ss[u].clear();
	//~ ss[u].insert({sub[u], d[u]});
	
	for(auto v : edges[u]){
		if(v == p) continue;
		dfs1(v, u);
		//~ if((int)ss[u].size() < (int)ss[v].size()) swap(ss[u], ss[v]);
		for(auto x : ss[v]){
			auto it = ss[u].lower_bound({x[0], -1});
			if(it != ss[u].end()){
				//~ cout<<x[0]<<" "<<x[1]<<" "<<(*it)[0]<<" "<<(*it)[1]<<endl; //<<" "<<d[u]<<endl;
				rr[x[0] * 2] = max(rr[x[0] * 2], (*it)[1] + x[1] - d[u] * 2 + 1);
			}
		}
		
		for(auto x : ss[v]){
			add(x);
		} ss[v].clear();
	}
	add({sub[u], d[u]});
	
	//~ cout<<u<<endl;
	//~ for(auto x : ss[u]) cout<<x[0]<<" "<<x[1]<<endl;
	//~ cout<<endl;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	dfs(1, 1);
	dfs1(1);
	for(int i=n;i>0;i--){
		rr[i] = max(rr[i], rr[i+1]);
	}
	for(int i=1;i<=n;i++){
		if(i&1) { cout<<1<<"\n"; continue; }
		cout<<rr[i]<<"\n";
	}
}
 
 

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