题目描述

给定一棵树，对于树的每一层，你都可以切断一条边，使得这个树最后联通的点最少。(详见题目)

算法1

看到你们dfs删除的都是边的编号，我dfs删除的是具体的点,我觉得相对好理解一些,详情见代码

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
const ll N=2e3+5;
ll h[N],e[N],ne[N],idx;
vector<ll> res[N];//这个是用来存储每一层都有哪些点，不是边的编号，是具体的点
ll re[N];//存储每一个点的爹是谁
ll vis[N];//记录每一个点能不能走
ll ans[N];//记录每一个点下面的子树有多少个点
ll kk=0x3f3f3f3f3f3f3f3f;
void add(ll a,ll b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;//邻接表不解释
}
ll dfs(ll x,ll y,ll father)
{
    res[y].push_back(x);//y代表的是层数，x代表的是点，也就是说y层有哪些点存储在res里
    ans[x]=1;
    re[x]=father;//记录每个点的爹是谁
    for(int i=h[x];i!=-1;i=ne[i])
    {
        ll j=e[i];
        if(j==father)
        {
           continue;         
        }
        ans[x]+=dfs(j,y+1,x);
    }
    return ans[x];
}
void dfs_draw(ll x,ll y,ll father)
{
    vis[x]=y;//这个点被删除了，也就是说这个点连接这个点的爹的边被删除了，那么它下面的所有点都不用在dfs里面考虑了，所以把他们都标记为1
    for(int i=h[x];i!=-1;i=ne[i])
    {
        ll j=e[i];
        if(j==father)
        {
            continue;
        }
        dfs_draw(j,y,x);//j代表下一个点是谁，x代表j的爹是谁
    }
}
void dfs_k(ll x,ll y)
{
    kk=min(kk,y);//每次记录答案的最小值
    for(int i=0;i<res[x].size();i++)
    {
        ll j=res[x][i];//这个代表在第x层都有哪些点可以被我们枚举删除
        if(vis[j])//这个点在前面已经被切断，或者说是某个切断点的子树中的点，那么就不用考虑了
        {
            continue;
        }
        dfs_draw(j,1,re[j]);//基本操作，re[j]代表的是j的爹
        dfs_k(x+1,y-ans[j]);//x+1代表x这一层已经考虑过了，那么就dfs下一层去考虑
        dfs_draw(j,0,re[j]);//恢复现场
    }
}
int main()
{
    memset(h,-1,sizeof(h));
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        ll x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,1,-1);//从1号点开始，层数为1，1号点的爹为-1
    vis[1]=1;//1号点已经被记录了。
    dfs_k(2,n);//这个要从第二层开始考虑，因为第一层只有1个1，而1的病毒源点，不能切断，换句话说，本题保证除了1以外的一些点不被感染(通过切断边的方式),1必被感染的
    cout<<kk<<'\n';
    return 0;
}