Submission #40708151

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=2e5+10,INF=1e9;
void tomax(int& x,int y){x=max(x,y);}
void tomin(int& x,int y){x=min(x,y);}

int n,f[MAXN][2],ss[MAXN],son;
vector<int>e[MAXN];

typedef array<int,2> info;
info pre[MAXN],suf[MAXN];

void upd(info& x,int v){
	if(v>x[0])x[1]=x[0],x[0]=v;
	else if(v>x[1])x[1]=v;
}

void do_solve(int u,int i){
	rep(j,2,son){
		int len=f[ss[1]][1] + f[ss[j]][1]-1;

		tomax(len,pre[j-1][0] + 1 + pre[j-1][1]);
		tomax(len,suf[j+1][0] + 1 + suf[j+1][1]);
		tomax(len,pre[j-1][0] + 1 + suf[j+1][0]);
		tomax(len,max(f[ss[1]][1],f[ss[j]][1]) + max(pre[j-1][0],suf[j+1][0]));

		if(len<=i){
			int mx=max(f[ss[1]][1],f[ss[j]][1]);
			tomax(mx,pre[j-1][0]+1);tomax(mx,suf[j+1][0]+1);

			tomin(f[u][0],mx);
		}
	}
}

void dfs(int u,int fa,int i){
	son=0;
	for(auto v:e[u])if(v!=fa){
		dfs(v,u,i);
		son++;
	}
	if(!son){
		f[u][0]=f[u][1]=1;
		return;
	}

	son=0;
	for(auto v:e[u])if(v!=fa)ss[++son]=v;

	
	//做两轮冒泡排序
	rep(j,1,min(2,son)){
		per(k,son,j+1){
			if(f[ss[k]][0] > f[ss[k-1]][0])swap(ss[k],ss[k-1]);
		}
	}

	pre[0]=suf[son+1]={0,0};
	rep(j,1,son)pre[j]=pre[j-1],upd(pre[j],f[ss[j]][0]);
	per(j,son,1)suf[j]=suf[j+1],upd(suf[j],f[ss[j]][0]);

	//新颜色
	if(pre[son][0] + pre[son][1] + 1 <= i){
		tomin(f[u][1],pre[son][0]+1);
	}
	//只和一个儿子合并
	rep(j,1,son){
		int len=f[ss[j]][1]+pre[j-1][0];
		tomax(len,f[ss[j]][1]+suf[j+1][0]);
		tomax(len,pre[j-1][0]+pre[j-1][1]+1);
		tomax(len,suf[j+1][0]+suf[j+1][1]+1);
		tomax(len,pre[j-1][0]+suf[j+1][0]+1);

		if(len<=i){
			int mx=f[ss[j]][1];
			tomax(mx,pre[j-1][0]+1);tomax(mx,suf[j+1][0]+1);

			tomin(f[u][1],mx);
		}
	}

	if(son>1){
		//和两个儿子合并，则至少有一个是ss[1]或者ss[2]
		pre[1]={0,0};
		rep(j,2,son)pre[j]=pre[j-1],upd(pre[j],f[ss[j]][0]);
		do_solve(u,i);

		swap(ss[1],ss[2]);
		pre[1]={0,0};
		rep(j,2,son)pre[j]=pre[j-1],upd(pre[j],f[ss[j]][0]);
		do_solve(u,i);
	}

	tomin(f[u][0],f[u][1]);
}

int check(int mid){
	rep(i,1,n){
		f[i][0]=f[i][1]=INF;
	}
	dfs(1,0,mid);
	return f[1][0]!=INF || f[1][1]!=INF;
}

int main(){
	ios::sync_with_stdio(false);

	cin>>n;
	rep(i,1,n-1){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}

	int L=1,R=40,res=0;
	while(L<=R){
		int mid=(L+R)>>1;
		if(check(mid)){
			res=mid;R=mid-1;
		}else{
			L=mid+1;
		}
	}
	cout<<res<<endl;
    return 0;
}

Submission Info

Judge Result