记录编号	137531	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]城市改建	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.929 s
提交时间	2014-11-04 21:02:23	内存使用	19.77 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int SIZEN=300010,INF=0x7fffffff/2;
int N;
vector<int> c[SIZEN];
vector<int> Blis;//BFS序列
vector<int> son[SIZEN];
int fa[SIZEN]={0};
int f[SIZEN],g[SIZEN];
//f[i]:i子树的直径,g[i]:i子树中离x的最远距离
int h[SIZEN],p[SIZEN];
//h[i]:去掉i子树后剩下那一坨的直径,p[i]:i离子树外最远点的距离
void update(int &a,int &b,int c){//a优先于b更新,求最大值
	if(c>a) b=a,a=c;
	else if(c>b) b=c;
}
int max_two(int a,int b,int c,int d){//a>=b,c>=d
	if(a<c) swap(a,c);
	return a+max(c,max(b,d));
}
class STATE{
public:
	int fmx;
	int gmx1,gmx2;
	void renew(STATE s){
		fmx=max(fmx,s.fmx);
		update(gmx1,gmx2,s.gmx1);
		update(gmx1,gmx2,s.gmx2);
	}
	void clear(void){
		fmx=0;
		gmx1=gmx2=-INF;
	}
};
STATE pre[SIZEN],suf[SIZEN];
void calc_hp(int x){
	for(int i=0;i<son[x].size();i++){
		pre[i].clear();
		pre[i].fmx=f[son[x][i]],pre[i].gmx1=g[son[x][i]];
		if(i) pre[i].renew(pre[i-1]);
	}
	for(int i=son[x].size()-1;i>=0;i--){
		suf[i].clear();
		suf[i].fmx=f[son[x][i]],suf[i].gmx1=g[son[x][i]];
		if(i+1<son[x].size()) suf[i].renew(suf[i+1]);
	}
	for(int i=0;i<son[x].size();i++){
		int u=son[x][i];
		//算p
		p[u]=p[x]+1;
		if(i>0) p[u]=max(p[u],pre[i-1].gmx1+2);
		if(i+1<son[x].size()) p[u]=max(p[u],suf[i+1].gmx1+2);
		//算h
		h[u]=h[x];//直径不经过父亲且在其上方
		h[u]=max(h[u],p[x]);
		if(i>0){
			h[u]=max(h[u],pre[i-1].fmx);//直径不经过父亲,在一个兄弟子树内
			h[u]=max(h[u],pre[i-1].gmx1+1+p[x]);//直径经过父亲,一头在兄弟子树内一头在父亲上方
			h[u]=max(h[u],pre[i-1].gmx1+pre[i-1].gmx2+2);//直径经过父亲,两头在两个前面的兄弟子树内
		}
		if(i+1<son[x].size()){
			h[u]=max(h[u],suf[i+1].fmx);
			h[u]=max(h[u],suf[i+1].gmx1+1+p[x]);
			h[u]=max(h[u],suf[i+1].gmx1+suf[i+1].gmx2+2);
		}
		if(i>0&&i+1<son[x].size())
			h[u]=max(h[u],max_two(pre[i-1].gmx1,pre[i-1].gmx2,suf[i+1].gmx1,suf[i+1].gmx2)+2);
	}
}
void calc_fg(int x){
	f[x]=g[x]=0;
	int mx1=-INF,mx2=-INF;
	for(int i=0;i<son[x].size();i++){
		int u=son[x][i];
		fa[u]=x;
		f[x]=max(f[x],f[u]);
		g[x]=max(g[x],g[u]+1);
		update(mx1,mx2,g[u]);
	}
	f[x]=max(f[x],g[x]);
	f[x]=max(f[x],mx1+mx2+2);
}
void DP(void){
	for(int i=N-1;i>=0;i--) calc_fg(Blis[i]);
	for(int i=0;i<N;i++) calc_hp(Blis[i]);
}
void answer(void){
	int ans=INF;
	for(int i=2;i<=N;i++){//删去连接i和fa[i]的边
		int tmp=max(f[i],h[i]);
		tmp=max(tmp,(f[i]+1)/2+(h[i]+1)/2+1);
		ans=min(ans,tmp);
	}
	printf("%d\n",ans);
}
queue<int> Q;
void BFS(int s){
	Q.push(s);
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		Blis.push_back(x);
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i];
			if(u==fa[x]) continue;
			son[x].push_back(u);
			fa[u]=x;
			Q.push(u);
		}
	}
}
void read(void){
	scanf("%d",&N);
	int a,b;
	for(int i=1;i<N;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
		c[b].push_back(a);
	}
}
int main(){
	freopen("nt2012_stx_tree.in","r",stdin);
	freopen("nt2012_stx_tree.out","w",stdout);
	read();
	BFS(1);
	DP();
	answer();
	return 0;
}