记录编号	330879	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-10-26 21:28:57	内存使用	0.32 MiB

#include<cstdio>
#include<queue>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("epidemic.in","r",stdin);freopen("epidemic.out","w",stdout);chul();Cu;
using namespace std;
const int maxn=310;
int tim,size[maxn],son[maxn],head[maxn],fath[maxn],rehead[maxn];
struct op{
	int to,next;
}r[maxn<<2];
queue<int> q[2];
void insert(int fr,int to){
	tim++;
	r[tim].to=to;
	r[tim].next=rehead[fr];
	rehead[fr]=tim;
}
void reinsert(int fr,int to){
	tim++;
	r[tim].to=to;
	r[tim].next=head[fr];
	head[fr]=tim;
}
void dfs(int rt){
	size[rt]=1;
	int y;
	for(int i=rehead[rt];i;i=r[i].next){
		son[rt]++;
		y=r[i].to;
		if(fath[rt]==y)continue;
		fath[y]=rt;
		reinsert(rt,y);
		dfs(y);
		size[rt]+=size[y];
	}
}
void chul(){
	int n,p,s,t;
	scanf("%d%d",&n,&p);
	for(int i=1;i<n;i++){
		scanf("%d%d",&s,&t);
		insert(s,t);
		insert(t,s);
	}
	dfs(1);
	bool tet=0;
	q[tet].push(1);
	int cnt=n-1;
	int x,y;
	int ans=0,cut=0,lastcut=0;
	while(cnt){
		lastcut=cut;
		cut=0;
		while(!q[tet].empty()){
			x=q[tet].front();	
			q[tet].pop();
			if(x==lastcut)continue;
			for(int i=head[x];i;i=r[i].next){
				y=r[i].to;
				if(son[y]*3+size[y]*2>=son[cut]*3+size[cut]*2)cut=y;
				q[!tet].push(y);
				cnt--;
				ans++;
			}
		}
		cnt=cnt+1-size[cut];
		ans--;
		tet=!tet;
	}
	printf("%d\n",ans+1);
}
int main(){
	Begin;
chul();while(1);
}