# POJ 1947 Rebuilding Roads （树形dp）

## Description

The cows have reconstructed Farmer John’s farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn’t have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree.

Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 <= P <= N) barns from the rest of the barns.

## Input

Line 1: Two integers, N and P

Lines 2..N: N-1 lines, each with two integers I and J. Node I is node J’s parent in the tree of roads.

## Output

A single line containing the integer that is the minimum number of roads that need to be destroyed for a subtree of P nodes to be isolated.

## Sample Input

11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11


## Sample Output

2


## 思路

dp[root][i] 代表以 root 为根节点的子树中保留 i 个节点所要切除的最小边数。

## AC 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
typedef __int64 LL;

const int maxn = 200;
struct node
{
int u;
int v;
int next;
} a[maxn];
int dp[maxn][maxn];     //dp[root][j] 代表以 root 为根的子树保留 j 个节点所需要的最小切割次数
int num[maxn];

void addedge(int u,int v)   // 链式前向星建图
{
a[cnt].u=u;
a[cnt].v=v;
}
int n,p;

int dfs(int x)
{
int sum=1;
for(int i=head[x]; i!=-1; i=a[i].next)  // 遍历子节点
{
int son=a[i].v;
sum+=dfs(son);  // 求当前已知节点的个数
for(int j=sum; j>0; j--)    // 计算 dp[x][j]
for(int s=1; s<j; s++)  // 分配 s 个节点给 dfs 出的新枝
dp[x][j]=min(dp[x][j-s]+dp[son][s]-1,dp[x][j]);
}
return sum;
}

void init()
{
memset(dp,INF,sizeof(dp));
memset(num,0,sizeof(num));
cnt=0;
}

int main()
{
while(~scanf("%d%d",&n,&p))
{
init();
for(int i=1; i<n; i++)
{
int a,b;
scanf("%d%d",&a,&b);