传染病控制

题目大意

一棵树，每次可以删掉一个节点及其子节点，同时从第一层节点开始，每次每层节点会被打上标记，求最小打上标记的个数

算法

由数据范围<=300得知，此题可以爆搜

然后就开始爆搜

#include <cstdio>
#include <vector>
#define int long long
struct edge{
    int to,nxt;cpp
}e[1000];
int head[500]={0},cnt=0;
void add(int u,int v){
    e[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
    e[++cnt]=(edge){u,head[v]};
    head[v]=cnt;
}
std::vector<int> count[500];
int depth[500]={0};
int mx=0,ans=1<<30;
int size[500]={0};
void dfs(int t,int d){
    if(d>mx)
        mx=d;
    depth[t]=d;
    count[d].push_back(t);
    size[t]=1;
    for(int i=head[t];i;i=e[i].nxt){
        if(depth[e[i].to])
            continue;
        dfs(e[i].to,d+1);
        size[t]+=size[e[i].to];
    }
}
int n,p;
bool f[500]={false};
void redo(int t){
    f[t]=true;
    for(int i=head[t];i;i=e[i].nxt)
        if(depth[e[i].to]>depth[t])
            redo(e[i].to);
}
void undo(int t){
    f[t]=false;
    for(int i=head[t];i;i=e[i].nxt)
        if(depth[e[i].to]>depth[t])
            undo(e[i].to);
}
void dfs2(int t,int sum){
    // printf("%d\n",t);
    // for(int i=1;i<=n;i++)
        // printf("%d ",f[i]);
    // printf("\n");
    if(sum<ans)
        ans=sum;
    // printf(":%lld %lld %lld\n",t,sum,ans);
    for(int i:count[t]){
        // printf("233:::%d %d\n",i,t);
        if(f[i])
            continue;
        redo(i);
        dfs2(t+1,sum-size[i]);
        undo(i);
    }
}
signed main(){
    scanf("%lld%lld",&n,&p);
    for(int i=1;i<=p;i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
    }
    dfs(1,1);
    // for(int i=1;i<=mx;i++){
        // printf("%lld:",i);
        // for(int j:count[i])
            // printf("%lld ",j);
        // printf("\n");
    // }
    // for(int i=1;i<=n;i++)
        // printf("%lld ",size[i]);
    // printf("\n");
    dfs2(2,n);
    printf("%lld\n",ans);
    return 0;
}