思路:
题目想问的是:
有一棵树;
对于除1外每个深度可以剪掉一棵子树;
问最后剩下多少节点;
题目意思一简单,这个题立马就变水了;
搜索就能ac;
数据有为链的情况,按深度为层次搜索的话要记得提前记录答案并return;
来,上代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 305
#define maxm 90005
#define INF 0x7fffffff int n,m,head[maxn],E[maxm],V[maxm],cnt,ans=INF,dep[maxn];
int l[maxn],r[maxn],size[maxn],map[maxn][maxn],deepest; bool if_[maxn]; inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} inline void edge_add(int u,int v)
{
E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
} void pre(int now,int fa,int deep)
{
deepest=max(deep,deepest),dep[now]=deep;
map[deep][++size[deep]]=now,l[now]=++cnt;
for(int i=head[now];i;i=E[i])
{
if(V[i]==fa) continue;
pre(V[i],now,deep+);
}
r[now]=cnt;
} void dfs(int now,int ans_)
{
if(ans_>=ans) return ;
if(now==deepest)
{
ans=ans_;
return ;
}
int pos=-;
for(int i=;i<=size[now+];i++) if(!if_[l[map[now+][i]]]) pos++;
if(pos==-)
{
ans=min(ans,ans_);
return ;
}
for(int v=;v<=size[now];v++)
{
if(if_[l[map[now][v]]]) continue;
for(int i=head[map[now][v]];i;i=E[i])
{
if(dep[V[i]]>dep[now]&&!if_[l[V[i]]])
{
for(int j=l[V[i]];j<=r[V[i]];j++) if_[j]=true;
dfs(now+,ans_+pos);
for(int j=l[V[i]];j<=r[V[i]];j++) if_[j]=false;
}
}
}
} int main()
{
in(n),in(m);int u,v;
while(m--)
{
in(u),in(v);
edge_add(u,v);
}
cnt=,pre(,,),dfs(,);
cout<<ans;
return ;
}