题解 P1272 【重建道路】
beretty
2017-11-03 06:50:53
```cpp
//树形DP
//大致思路：
//递归操作，f[i][j]表示保留i为根的子节点。
//c数组记录点的度。
//因为这是一棵树，所以每个点的度为1
//然后随便设一个根，我设的1为根，1的根就为0.
//递归时传入两个参数，为当前节点和当前节点的根。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
```
# define LL 153
```cpp
int hea[LL],num,n,p,a,b,c[LL],f[LL][LL],r[LL];
int ans=0x3f3f3f3f;
struct edge{
int nex,to;
}edge[LL<<1];
void add_edge(int from,int to)
{
edge[++num].nex=hea[from];
edge[num].to=to;
hea[from]=num;
}
void dfs(int u,int root)
{
int i,j,k;
f[u][1]=c[u];//只选这个根自己需要切掉几条边。。
for(i=hea[u];i;i=edge[i].nex)
if(edge[i].to!=root)//如果是根就不要搜了
{
dfs(edge[i].to,u);
for(j=p;j>=1;j--)
for(k=1;k<j;k++)
f[u][j]=min(f[u][j],f[u][k]+f[edge[i].to][j-k]-2);// emmm,至于为什么-2.。个人认为本题最坑的一点，害的我想了好久，一定是我太菜了，因为在初始化的时候已经把所有与u和edge[i].to相连接的节点给砍掉了，但是u和edge[i].to相连的的度应该保留，而这段相连的度，在u中加了一次，在edge[i].to中也加了一次，所以应该-2。
}
}
int main()
{
int i,j;
scanf("%d%d",&n,&p);
for(i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
c[a]++,c[b]++;//记录a,b的度。
add_edge(a,b),add_edge(b,a);//建双向边，因为1也不是这棵树的真根，只是因为方便设的。
}
memset(f,0x3f,sizeof(f));
dfs(1,0);
for(i=1;i<=n;i++) ans=min(f[i][p],ans);
printf("%d\n",ans);
return 0;
}
```