注意不一定要k==maxi+1时统计ans，应每一层都统计。因为每一层都可能割完。（例如#4，一条链）

否则WA#4&&#9

#include<cstdio>
#include<cstring>
#include<vector>
#define MAXN 305

inline int max(int x,int y){return x>y?x:y;}

int n,p,cnt,maxi,ans,head[MAXN],dep[MAXN],size[MAXN],fa[MAXN];

bool cut[MAXN];

std::vector<int> node[MAXN];

struct edge{
    int v,next;
}e[MAXN<<1];

inline void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

inline void deal_first(int u,int fau){
    fa[u]=fau;
    dep[u]=dep[fau]+1;
    size[u]=1;
    node[dep[u]].push_back(u);
    maxi=max(maxi,dep[u]);
    for(int i=head[u];i!=-1;i=e[i].next){
        if(e[i].v==fau)continue;
        deal_first(e[i].v,u);
        size[u]+=size[e[i].v];
    }
}

inline void dfs(int k,int tot){
    ans=max(ans,tot);//
    if(k==maxi+1){
        return;
    }
    for(int i=0;i<node[k].size();i++){
        if(cut[fa[node[k][i]]])cut[node[k][i]]=1;
        else cut[node[k][i]]=0;
    }
    for(int i=0;i<node[k].size();i++){
        if(cut[node[k][i]])continue;
    //  printf("%d %d\n",node[k][i],cut[node[k][i]]);
        cut[node[k][i]]=1;
        dfs(k+1,tot+size[node[k][i]]);
        cut[node[k][i]]=0;
    }
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&p);
    for(int i=1;i<=p;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    deal_first(1,0);
    dfs(2,0);
    printf("%d\n",n-ans);
}

传染病控制

原文：https://www.cnblogs.com/Y15BeTa/p/11728577.html