记录编号	293211	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.186 s
提交时间	2016-08-09 20:00:21	内存使用	0.66 MiB

#include<cstdio>
const int maxn=305;
struct edge{
	int to,next;
}lst[maxn<<1];int len=1;
int first[maxn];
void addedge(int a,int b){
	lst[len].to=b;
	lst[len].next=first[a];
	first[a]=len++;
}
bool used[maxn];
int depth[maxn],_s[maxn],prt[maxn];
int dict[maxn][maxn],Max[maxn],cnt[maxn];
void cover(int x){
	used[x]=true;
	for(int pt=first[x];pt;pt=lst[pt].next){
		if(lst[pt].to==prt[x])continue;
		cover(lst[pt].to);
	}
}
void uncover(int x){
	used[x]=false;
	for(int pt=first[x];pt;pt=lst[pt].next){
		if(lst[pt].to==prt[x])continue;
		uncover(lst[pt].to);
	}
}
int max(int a,int b){
	return a>b?a:b;
}
void dfs1(int x){//预处理必要的信息,如每个点的深度,子树大小 
	dict[depth[x]][++dict[depth[x]][0]]=x;
	_s[x]=1;
	for(int pt=first[x];pt;pt=lst[pt].next){
		if(lst[pt].to==prt[x])continue;
		depth[lst[pt].to]=depth[x]+1;
		prt[lst[pt].to]=x;
		dfs1(lst[pt].to);
		_s[x]+=_s[lst[pt].to];
	}
	Max[depth[x]]=max(Max[depth[x]],_s[x]);
}
void _dfs1(int rt){
	dict[depth[rt]][++dict[depth[rt]][0]]=rt;
	_s[rt]=1;
	for(int pt=first[rt];pt;pt=lst[pt].next){
		if(lst[pt].to==prt[rt])continue;
		prt[lst[pt].to]=rt;
		depth[lst[pt].to]=depth[rt]+1;
		dfs1(lst[pt].to);
		_s[rt]+=_s[lst[pt].to];
	}
}

int dfs2(int dep){
	int ans=0;
	int v;
	for(int i=1;i<=dict[dep][0];++i){
		v=dict[dep][i];
		if(!used[v]){
			cover(v);
			ans=max(ans,_s[v]+dfs2(dep+1));
			uncover(v);
		}
	}
	return ans;
}
int main(){
	freopen("epidemic.in","r",stdin);
	freopen("epidemic.out","w",stdout);
	int n,p;scanf("%d %d",&n,&p);
	int a,b;
	for(int i=1;i<n;++i){
		scanf("%d %d",&a,&b);
		addedge(a,b);addedge(b,a);
	}
	depth[1]=1; 
	dfs1(1);
	for(int i=n;i>=1;--i){
		Max[i]+=Max[i+1];//Max[i]:从深度为i开始每一层选最大子树的最优结果 
	}
	printf("%d\n",n-dfs2(2));
	fclose(stdin);fclose(stdout);
	return 0;
}