应该是属于偏简单的一类树形DP了。思路很明确，dp[ i ][ n ]表示以i为根节点的子树中取n个点的子树所需的最小代价（所需删的边数）。那么对于一个节点 i 有dp[ i ][ 1 ] = 0，那么对于其儿子节点 j 就有大致两种情况了：①根本不取 j 子树上的，此时代价为dp[ i ][ n ]+1（即删除 i 到 j 的这条边）；②取 j 子树上的 k 个节点那么代价就是dp[ i ][ n - k] + dp[ j ][ k ]。我们每次在这两者之间取最小值就是了。
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
int head[200],flag[200];
int N,P;
int dp[200][200];
struct NODE
{
int to,next;
}edge[5000];
void dfs(int x)
{
int i,j,k,to,temp;
for(i=0;i<=P;i++) dp[x][i]=1000000;
dp[x][1]=0;
for(i=head[x];i!=-1;i=edge[i].next)
{
to=edge[i].to;
dfs(to);
for(j=P;j>0;j--)
{
temp=dp[x][j]+1;
for(k=1;k