记录编号	287041	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2016-08-01 14:53:03	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=310;
struct edge{
	int to;
	edge *prev;
	edge():to(0),prev(NULL){}
}ee[maxn<<1];
void insert(int,int);
void dfs(int);
void bfs(int);
int len=0,n,size[maxn],prt[maxn]={0},son[maxn]={0},x,y,ans=0;
edge *last[maxn]={NULL};
inline int MAIN(){
	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	scanf("%d%*d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
	}
	size[0]=0;
	son[0]=-1;
	dfs(1);
	bfs(1);
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
void dfs(int x){
	int y;
	size[x]=1;
	for(edge *e=last[x];e;e=e->prev){
		y=e->to;
		if(y==prt[x])continue;
		son[x]++;
		prt[y]=x;
		dfs(y);
		size[x]+=size[y];
	}
}
void bfs(int x){//用的是贪心，每次切掉儿子最多的点，然而正确性不会证明
	int y;
	queue<int>q;
	vector<int>v;
	q.push(x);
	for(;;){
		v.clear();
		while(!q.empty()){
			x=q.front();
			q.pop();
			ans++;
			for(edge *e=last[x];e;e=e->prev){
				y=e->to;
				if(y==prt[x])continue;
				v.push_back(y);
			}
		}
		y=0;
		if(v.empty())break;
		for(vector<int>::iterator it=v.begin();it!=v.end();it++)
			if(size[*it]*2+(son[*it]*3)>size[y]*2+(son[y]*3))y=*it;
		for(vector<int>::iterator it=v.begin();it!=v.end();it++)
			if(y!=*it)q.push(*it);
	}
}
int hzoier=MAIN();
int main(){;}
/*
7 6
1 2
1 3
2 4
2 5
3 6
3 7
Answer:
3
*/
/*
13 12
1 2
1 3
1 4
2 5
2 7
5 6
5 9
9 13
4 10
4 11
4 12
11 8
Answer:
4
*/