【Luogu1272】重建道路（动态规划）
题面
题目描述
一场可怕的地震后，人们用N个牲口棚(1≤N≤150，编号1..N)重建了农夫John的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。John想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有P(1≤P≤N)个牲口棚的子树和剩余的牲口棚分离，John想知道这些道路的最小数目。
输入输出格式
输入格式：
第1行：2个整数，N和P
第2..N行：每行2个整数I和J，表示节点I是节点J的父节点。
输出格式：
单独一行，包含一旦被破坏将分离出恰含P个节点的子树的道路的最小数目。
输入输出样例
输入样例#1：
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
输出样例#1：
2
题解
树型DP
设(f[i][j])表示当前以(i)为根节点，保留(j)个节点的最小代价
转移有所有子树的值转移过来
其中(f[i][1]=degree[i])，其中(degree)表示出度
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 300
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Line
{
int v,next;
}e[MAX<<1];
int lk[MAX];
int h[MAX],cnt=1;
int size[MAX],n,p,ans=1e9;
inline void Add(int u,int v)
{
e[cnt]=(Line){v,h[u]};
h[u]=cnt++;lk[u]++;
}
int f[MAX][MAX];
void DFS(int u,int ff)
{
size[u]=1;f[u][1]=lk[u]-(ff!=0);
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==ff)continue;
DFS(v,u);
for(int j=p;j;--j)
for(int k=1;k<=j;++k)
f[u][j]=min(f[u][j],f[v][k]+f[u][j-k]-1);
}
ans=min(ans,f[u][p]+(ff!=0));
}
int main()
{
n=read();p=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
Add(u,v);Add(v,u);
}
memset(f,63,sizeof(f));
DFS(1,0);
cout<<ans<<endl;
return 0;
}