【20180809】集训题d3

考场上没想到好的解法，敲了个60分暴力。

用二分，随便提一个节点为根，二分答案，深度最深的节点一定要被照顾到，所以最深的点往上跳答案层即可，和其距离答案以内的点都删掉，再做一次。时间复杂度O（nlogn）。有更快的O（n）做法，要用树形dp。

#include<bits/stdc++.h>
using namespace std;
struct Info{int nu,ne;}a[400010];
int n,x,y,b[200010],z,f[200010],d[200010],num;
bool vi[200010];
template <typename T> void read(T &x) {
	x=0;char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=x*10+c-'0';
}
void jb(int x,int y){a[++num].nu=y;a[num].ne=b[x];b[x]=num;}//加边 
void dfs(int x,int fa,int dep){
	d[x]=dep;f[x]=fa;
	for (int y=b[x];y;y=a[y].ne){
		if (a[y].nu!=fa)dfs(a[y].nu,x,dep+1);
	}
}//预处理 
void dfs1(int x,int fa,int di,int mdi){
	vi[x]=false;if (di==mdi) return ;
	for (int y=b[x];y;y=a[y].ne){
		if (a[y].nu!=fa) dfs1(a[y].nu,x,di+1,mdi);
	}
}
bool pan(int x){
	y=z;
	for (int i=1;i<=n;i++) vi[i]=true;
	for (int i=1;i<=x;i++)y=f[y];
	dfs1(y,0,0,x);
	y=0;
	for (int i=1;i<=n;i++)if(vi[i]&&d[i]>d[y])y=i;
	for (int i=1;i<=x;i++)if (f[y]!=0)y=f[y];
	dfs1(y,0,0,x);
	for (int i=1;i<=n;i++) if (vi[i]) return false;
	return true;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<n;i++){read(x);read(y);jb(x,y);jb(y,x);}
	dfs(1,0,1);
	for (int i=1;i<=n;i++) if (d[i]>d[z])z=i;
	int l=0,r=d[z]-1,mid;
	while (l+1<r){
		mid=(l+r)/2;
		if (pan(mid))r=mid;else l=mid;
	}
	if (pan(l))cout<<l<<endl;else cout<<r<<endl;
	return 0;
}