這是一個孩子之間有分配的樹形動態規劃問題，一般解決的方法爲左孩子右兄弟法或孩子揹包分配。

左孩子右兄弟表示法中，狀態設定爲

F[i,j]表示以i爲根的子樹以及以i右邊兄弟爲根的子樹中選j個點需要刪除邊的最少數量。F[i,j]還隱含了i的父親已經被選，否則i是不可能被選的。

狀態轉移方程爲

F[i][j] = Min { F[i.brother][j] + 1 (不選節點i) F[i.child][k] + F[i.brother][j-k-1] (選節點i) 0<=k<=i子樹及兄弟子樹大小-1 且 k<=j-1 }

邊界條件

F[i][0] = F[i.brother][0] + 1 節點0爲一個虛構的節點，如果節點i沒有兄弟(或兒子)，則它的兄弟(或兒子)爲0。 F[0][0]=0 F[0][j]=INF (j>0，INF爲一個極大的值)

目標狀態

左孩子右兄弟表示法的目標狀態表示不很直觀，一棵子樹分配P個節點，需要表示成子樹根第一個孩子及其兄弟分配P-1的節點。另外，如果不是根節點，還要增加1，表示與它的父節點的邊也斷掉。 Ans = Min{ F[根節點的第一個孩子][P-1] , F[非根節點的第一個孩子][P-1] + 1 }

如果用孩子揹包分配法，狀態可以表示爲

F[i][j]爲以i爲根的子樹中選擇j個節點要刪除邊的最少數量。

狀態轉移方程爲

F[i][j] = Min { Sigma{ F[i.child[k]][m[k]] } } 其中 sigma[m[k]] = j-1 直接在孩子中分配不易，需要再進行一次DP，運用揹包的思想，設狀態

G[a][b]爲對於特定的i時i的前i個孩子分配j個節點的最小值

G[a][b] = Min { G[a-1][b-k] + F[i.child[a]][k] }

於是F[i][j]可以表示爲 F[i][j] = G[i.childcount][j-1]

邊界條件爲

對於每個節點i G[0][0]=0 G[0][j]=INF (j>0 INF爲一個極大的值)

當i爲葉節點時 F[i][0]=1 F[i][1]=0

目標狀態

Ans = Min{ F[根節點][P] , F[非根節點][P] + 1}

對於這道題，兩種方法的時間複雜度均爲O(N^3)。左孩子右兄弟法的優點在於狀態轉移比較簡單，缺點是不夠直觀，尤其在表示目標狀態的時候，另外邊界情況的考慮也比較複雜，還有就是需要額外建樹。孩子揹包分配的方法優點是狀態直觀，易於表示，容易寫成非遞歸，缺點是狀態轉移較爲複雜，需要用一個揹包再分配一次。我個人比較傾向於孩子揹包分配法，除非必須，我一般都會寫成這樣的。

左孩子右兄弟

/* 
 * Problem: pku1947 Rebuilding Roads
 * Author: Guo Jiabao
 * Time: 2009.6.11 8:44
 * State: Solved
 * Memo: 樹形動態規劃 孩子兄弟
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=151,INF=0x7FFFFFF;
struct edge
{
    edge *next;
    int t;
}ES[MAXN*2],*V[MAXN];
struct TreeNode
{
    int child,brother,size;
}P[MAXN];
int N,K,EC,Ans,F[MAXN][MAXN];
inline void addedge(int a,int b)
{
    ES[++EC].next = V[a];
    V[a]=ES+EC; V[a]->t=b;
}
void buildtree(int i,int f)
{
    for (edge *e=V[i];e;e=e->next)
    {
        int j=e->t;
        if (j==f) continue;
        P[j].brother = P[i].child;
        P[i].child = j;
        buildtree(j,i);
    }
}
void calcsize(int i)
{
    if (i==0) return;
    calcsize(P[i].brother);
    calcsize(P[i].child);
    P[i].size = P[ P[i].brother ].size + P[ P[i].child ].size + 1;
}
inline int min(int a,int b)
{
    return a<b?a:b;
}
void init()
{
    int i,a,b;
    freopen("rr.in","r",stdin);
    freopen("rr.out","w",stdout);
    scanf("%d%d",&N,&K);
    for (i=1;i<N;i++)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
    buildtree(1,0);
    calcsize(1);
    memset(F,-1,sizeof(F));
}
int dp(int i,int j)
{
    int rs = F[i][j];
    if (rs==-1)
    {
        if (i==0)
        {
            if (j==0)
                rs = 0;
            else
                rs = INF;
        }
        else if (j==0)
            rs = dp(P[i].brother,0) + 1;
        else
        {
            rs = INF;
            rs = min(rs,dp(P[i].brother,j) + 1);
            for (int k=0;k<=P[i].size-1 && k<=j-1;k++)
                rs = min(rs,dp(P[i].child,k) + dp(P[i].brother,j-k-1));
        }
        F[i][j]=rs;
    }
    return rs;
}
void solve()
{
    int i;
    if (N==1)
        Ans = 0;
    else if (K==1)
        Ans = 1;
    else
    {
        Ans = dp(P[1].child,K-1);
        for (i=2;i<=N;i++)
            if (P[i].child)
                Ans = min(Ans,dp(P[i].child,K-1) + 1);
    }
}
int main()
{
    init();
    solve();
    printf("%dn",Ans);
    return 0;
}

孩子揹包分配

/* 
 * Problem: pku1947 Rebuilding Roads
 * Author: Guo Jiabao
 * Time: 2009.6.11 10:04
 * State: Solved
 * Memo: 樹形動態規劃 孩子鏈+揹包
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=151,INF=0x7FFFFFF;
struct edge
{
    edge *next;
    int t;
}ES[MAXN*2],*V[MAXN];
int N,K,EC,Ans,F[MAXN][MAXN],G[MAXN],Size[MAXN],A;
inline void addedge(int a,int b)
{
    ES[++EC].next = V[a];
    V[a]=ES+EC; V[a]->t=b;
}
inline int min(int a,int b)
{
    return a<b?a:b;
}
void init()
{
    int i,j,a,b;
    freopen("rr.in","r",stdin);
    freopen("rr.out","w",stdout);
    scanf("%d%d",&N,&K);
    for (i=1;i<N;i++)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
    for (i=1;i<=N;i++)
        for (j=1;j<=N;j++)
            F[i][j]=INF;
}
void dp(int i,int f)
{
    int j,k;
    edge *e;
    Size[i]=1;
    for (e=V[i];e;e=e->next)
    {
        j=e->t;
        if (j==f) continue;
        dp(j,i);
        Size[i] += Size[j];
    }
    if (Size[i]==1)
    {
        F[i][0]=1;
        F[i][1]=0;
    }
    else
    {
        for (j=1;j<=Size[i]-1;j++)
            G[j]=INF;
        G[0]=0;
        for (e=V[i];e;e=e->next)
        {
            if (e->t==f) continue;
            for (j=Size[i]-1;j>=0;j--)
            {
                A=INF;
                for (k=0;k<=Size[e->t] && k<=j;k++)
                {
                    A=min(A,G[j-k] + F[e->t][k]);
                }
                G[j]=A;
            }
        }
        F[i][0]=1;
        for (j=1;j<=Size[i];j++)
        {
            F[i][j] = G[j-1];
        }
    }
}
void solve()
{
    int i;
    dp(1,0);
    Ans = F[1][K];
    for (i=2;i<=N;i++)
        Ans = min(Ans,F[i][K]+1);
}
int main()
{
    init();
    solve();
    printf("%dn",Ans);
    return 0;
}