记录编号	442234	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]传染病控制	最终得分	100
用户昵称	xzz_233	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2017-08-26 17:05:06	内存使用	0.67 MiB

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<vector>
#define Fname "epidemic"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
    rg int x=0,f=1;rg char ch=getchar();
    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int maxn=310,maxm=maxn<<1;
int fir[maxn],nxt[maxm],dis[maxm];
int siz[maxn],dfn[maxn],k[maxn],s[maxn][maxn],ans=1e9,n;
il vd DFS(int now,int dep=1,int fa=-1){
    s[dep][++k[dep]]=now;
    siz[now]=1,dfn[now]=++dfn[0];
    erep(i,now)if(dis[i]^fa)DFS(dis[i],dep+1,now),siz[now]+=siz[dis[i]];
}
int tree[maxn];
il vd add(int p,int k){while(p<=n)tree[p]+=k,p+=p&-p;}
il int summ(int p){int ret=0;while(p)ret+=tree[p],p-=p&-p;return ret;}
il vd dfs(int now,int gg){
    if(gg>=ans)return;
    if(!k[now]){ans=gg;return;}
    int sum=0;
    rep(i,1,k[now])if(!summ(dfn[s[now][i]]))++sum;
    if(gg+sum-1>=ans)return;
    if(sum==1||sum==0){ans=min(ans,gg);return;}
    rep(i,1,k[now])if(!summ(dfn[s[now][i]])){
	add(dfn[s[now][i]],1);
	add(dfn[s[now][i]]+siz[s[now][i]],-1);
	dfs(now+1,gg+sum-1);
	add(dfn[s[now][i]],-1);
	add(dfn[s[now][i]]+siz[s[now][i]],1);
    }
}
int main(){
    freopen(Fname".in","r",stdin);
    freopen(Fname".out","w",stdout);
    n=gi();
    int m=gi(),id=0;
    rep(i,1,m){
	int a=gi(),b=gi();
	nxt[++id]=fir[a],fir[a]=id,dis[id]=b;
	nxt[++id]=fir[b],fir[b]=id,dis[id]=a;
    }
    DFS(1);
    dfs(2,1);
    printf("%d\n",ans);
    return 0;
}