新冠疫情时期更新：本题是错题，后来被证明没有靠谱的多项式复杂度的做法。测试数据非常的水，各种玄学做法都可以通过，不代表算法正确。因此本题题目和本题解仅供参考。

更新 `2021-08-08`

年代久远的题了。当年水平太低，所以有一些不正确的地方请提出。

原 code 中的 bfs 纯粹为了初始化，所以显得难懂，因为我们初始化这些东西一般都用 dfs。下面放新版 code，其他思路和原题解一样。

#include<bits/stdc++.h>
using namespace std;
namespace name
{
	typedef long long ll;
	const ll N=300+10,inf=21474838647;
	struct edge{ll nxt,to;}e[N*2];
	struct node
	{
		ll son[N],cnt;
		node(){cnt=0;}
	}s[N];
	ll head[N],cnt=0,n,m,ans=inf;
	ll dep[N],tag[N],maxd=1,dad[N];
	void add(ll a,ll b)
	{
		e[++cnt]=(edge){head[a],b};
		head[a]=cnt;
	}
	ll visitor(ll root,ll fa,ll t)
	{
		ll ret=1;
		tag[root]=t;
		for(ll i=head[root];i;i=e[i].nxt)
		{
			ll son=e[i].to;
			if(son==fa) continue;
			ret+=visitor(son,root,t);
		}
		return ret;
	}
	void init(ll root,ll fa)
	{
		for(ll i=head[root];i;i=e[i].nxt)
		{
			ll son=e[i].to;
			if(son==fa) continue;
			dep[son]=dep[root]+1;
			maxd=max(maxd,dep[son]);
			dad[son]=root;
			s[dep[son]-1].son[++s[dep[son]-1].cnt]=son;
			init(son,root);
		}
	}
	void dfs(ll step,ll now)
	{
		if(step>maxd)
		{
			ans=min(ans,now);
			return;
		}
		ll flag=1;
		for(ll i=1;i<=s[step].cnt;i++)
		{
			ll to=s[step].son[i];
			if(tag[to]) continue;
			flag=0;
			now-=visitor(to,dad[to],1);
			dfs(step+1,now);
			now+=visitor(to,dad[to],0);
		}
		if(flag)
		{
			ans=min(ans,now);
			return;
		}
	}
	void main()
	{
		ll a,b;
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=m;i++)
		{
			scanf("%lld%lld",&a,&b);
			add(a,b);add(b,a);
		}
		dep[1]=1;
		init(1,1);
		dfs(1,n);
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	name::main();
	return 0;
}

code

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int next,end;
}e[600+5];
struct sorter
{
	int mem[300+5],cnt;
}s[300+5];
struct tobfs
{
	int st,name,proot;
};//3个玄学结构体
queue<tobfs>q;
int n,p,head[300+5],cnt=0,v[300+5],maxs=0,ans=300+5,dad[300+5];
inline void add(int a,int b)
{
	e[++cnt]=(edge){head[a],b};
	head[a]=cnt;
}//为什么用链式前向星？因为我懒！
int visitor(int t,int root)
{
	int re=1;
	v[root]=t;
	for(int i=head[root];i;i=e[i].next)
	{
		int nxt=e[i].end;
		if(nxt!=dad[root])
			re+=visitor(t,nxt);
	}
	return re;
}
void bfs()
{
	q.push((tobfs){1,1,-1});
	while(!q.empty())
	{
		tobfs tmp=q.front();q.pop();
		s[tmp.st].mem[++s[tmp.st].cnt]=tmp.name;
		maxs=max(maxs,tmp.st);
		dad[tmp.name]=tmp.proot;
		for(int i=head[tmp.name];i;i=e[i].next)
		{
			int nxt=e[i].end;
			if(nxt!=tmp.proot)
				q.push((tobfs){tmp.st+1,nxt,tmp.name});
		}
	}
}
void dfs(int step,int num)
{
	if(step>maxs)
	{
		ans=min(ans,num);
		return;
	}
	bool flag=1;
	for(int i=1;i<=s[step].cnt;i++)
		if(!v[s[step].mem[i]])
		{
			flag=0;
			num-=visitor(1,s[step].mem[i]);
			dfs(step+1,num);
			num+=visitor(0,s[step].mem[i]);//回溯
		}
	if(flag)
	{
		ans=min(ans,num);
		return;
	}
}
int main()
{ 
	memset(s,0,sizeof(s));
	scanf("%d%d",&n,&p);
	for(int i=1;i<=p;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	bfs();
	dfs(2,n);//居然同时用到了bfs,dfs!
	printf("%d",ans);
	return 0;
}

思路

题意就是切掉一些子树，且每层只能且一次，求可保留的最少节点数。

然鹅，题目数据范围很小（ $1≤n≤300$ ），于是，爆搜是完全可以过的。

暴力出省一。

各变量的意义：

dad[]：记录一个节点的父亲。由于各种原因懒，建树用了建图的方式，而数据所说的传播途径不保证第一个是父亲，第二个是儿子，建了无向图；而在爬树的过程中，可能会返祖（从儿子又遍历到了父亲）。所以用它特判一下。
e[]：边，链式前向星。
s[]：记录每层的节点。s[i].mem[j]表示第 $i$ 层第 $j$ 个节点，s[i].cnt表示第 $i$ 层有多少节点。
结构体tobfs：分别表示第几层、节点编号、节点的父亲。
maxs：表示树的深度。
v[]：标记，是否被切掉了。