树形DP（Rebuilding Roads poj1947）

题意：给出一颗树，求要形成一颗元素个数是p的子树，最少要去掉多少边

#include"stdio.h"

#include"string.h"

#include"stdlib.h"

#include"algorithm"

#define M 222

#define inf 0x3f3f3f3f

using namespace std;

struct node

{

    int u,v,next;

}edge[M*2];

int t,head[M],dp[M][M],num[M],degree[M];

void init()

{

    t=0;

    memset(head,-1,sizeof(head));

}

void add(int u,int v)

{

    edge[t].u=u;

    edge[t].v=v;

    edge[t].next=head[u];

    head[u]=t++;

}

void dfs(int u,int f)//对于每个点的子树处理

{

    num[u]=1;

    dp[u][1]=degree[u];//对于每个点只取一个点

    for(int i=head[u];i!=-1;i=edge[i].next)

    {

        int v=edge[i].v;

        if(v==f)continue;

        dfs(v,u);

        num[u]+=num[v];

        for(int j=num[u];j>=1;j--)

        {

            for(int k=1;k+1<=j;k++)

            dp[u][j]=min(dp[u][j],dp[u][k]+dp[v][j-k]-2);

        }

    }

}

int main()

{

    int n,p,i;

    while(scanf("%d%d",&n,&p)!=-1)

    {

        init();

        memset(degree,0,sizeof(degree));

        for(i=1;i<n;i++)

        {

            int a,b;

            scanf("%d%d",&a,&b);

            add(a,b);

            add(b,a);

            degree[a]++;

            degree[b]++;

        }

        memset(dp,inf,sizeof(dp));

        dfs(1,1);

        int ans=inf;

        for(i=1;i<=n;i++)

        {

            if(ans>dp[i][p])

                ans=dp[i][p];

        }

        printf("%d\n",ans);

    }

}