Submission #623345

#	Time	Username	Problem	Language	Result	Execution time	Memory
623345		errorgorn	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	631 ms	120964 KiB

meetings2

//もう布団の中から出たくない
//布団の外は寒すぎるから
//布団の中から出たくない
//布団の中はあたたかすぎるから

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

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int INF=1e18;

struct dat{
	int a=-INF,b=-INF,c=-INF;
	int ab=-INF,bc=-INF;
	int abc=-INF;
	
	dat(){}
	dat(int v){
		a=v,b=-2*v,c=v;
		ab=-v,bc=-v;
		abc=0;
	}
};

dat merge(dat i,dat j){
	dat res;
	res.a=max(i.a,j.a);
	res.b=max(i.b,j.b);
	res.c=max(i.c,j.c);
	res.ab=max({i.ab,j.ab,i.a+j.b});
	res.bc=max({i.bc,j.bc,i.b+j.c});
	res.abc=max({i.abc,j.abc,i.ab+j.c,i.a+j.bc});
	return res;
}

struct node{
	int s,e,m;
	dat val;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int k){
		if (s==e) val=dat(k);
		else{
			if (i<=m) l->update(i,k);
			else r->update(i,k);
			val=merge(l->val,r->val);
		}
	}
} *root=new node(0,400005);

int n;
vector<int> al[200005];
int d[200005];
int ss[200005];
int small[200005];
vector<int> pos[200005];
int IDX=1;

void dfs(int i,int p){
	ss[i]=1;
	small[i]=1e9;
	pos[i].pub(IDX++);
	
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		dfs(it,i);
		ss[i]+=ss[it];
		small[i]=min(small[i],n-ss[it]);
		pos[i].pub(IDX++);
	}
	small[i]=min(small[i],ss[i]);
}

int ans[200005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	dfs(1,-1);
	
	//rep(x,1,n+1) cout<<small[x]<<" "; cout<<endl;
	
	vector<int> idx;
	rep(x,1,n+1) idx.pub(x);
	sort(all(idx),[](int i,int j){
		return small[i]<small[j];
	});
	
	rep(x,1,n+1) ans[x]=1;
	rep(x,n/2+1,1){
		while (!idx.empty() && x<=small[idx.back()]){
			int u=idx.back(); idx.pob();
			for (auto it:pos[u]) root->update(it,d[u]);
		}
		
		ans[2*x]=root->val.abc+1;
	}
	rep(x,1,n+1) cout<<ans[x]<<endl;
}

Compilation message (stderr)

meetings2.cpp: In constructor 'node::node(long long int, long long int)':
meetings2.cpp:63:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

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