【正经题解】传染病控制

思路：
1.dfs一遍，求出每个点的size，fa，deep；
2.按照deep将每个点存入vector中；
3.按照deep进行dffs求解答案；
dffs时切断某个点与fa的连线表示该点打上标记，表示不被感染，并减去该点size，每次进入下一层时，扫fa，如果fa被标记，则该点也被标记。
最后dffs结束的状态为 搜到比最深deep更深的一层，或搜到某层时该层的点已全部被打上标记。
记录dffs出的最小答案，输出

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,ans;
struct node{
	int to,nxt;
}e[805];
int head[305],cnt,fa[305],siz[305],deep[305],madep,in[305];
vector<int> k[305];
inline void add(int from,int to){
	e[++cnt]=(node){to,head[from]};
	head[from]=cnt;
}
void dfs(int x,int f,int dep){
	fa[x]=f;siz[x]=1;deep[x]=dep;
	madep=max(madep,dep);
	for(int i=head[x];i;i=e[i].nxt)
		if(e[i].to!=f){
			dfs(e[i].to,x,dep+1);
			siz[x]+=siz[e[i].to];
		}
}
void dffs(int dep,int now){
	if(dep==madep+1){
		ans=min(ans,now);
		return ;
	}
	for(int i=0;i<k[dep].size();++i)
		if(in[fa[k[dep][i]]])
			in[k[dep][i]]=1;
		else in[k[dep][i]]=0;
	bool f=1;
	for(int i=0;i<k[dep].size();++i)
		if(!in[k[dep][i]])f=0;
	if(f){
		ans=min(ans,now);
		return ;
	}
	for(int i=0;i<k[dep].size();++i){
		if(in[k[dep][i]])continue;
		in[k[dep][i]]=1;
		dffs(dep+1,now-siz[k[dep][i]]);
		in[k[dep][i]]=0;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0,1);
	for(int i=1;i<=n;++i)
		k[deep[i]].push_back(i);
	ans=n;
	dffs(2,n);
	printf("%d",ans);
	return 0;
}