DP解之，边界纠结了两个小时，不过还好一次AC，f[i][j]表示已节点已为根的有j个节点所需去掉的边，这个过程可由分组背包的思想来完成，确定最优解每个子树应该有的节点数。最后就是比较i（i为每个节点的编号）为根的保留p个节点的最小值，p为要保留的节点数。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 const int maxn=150+10; 6 const int inf=0x3f3f3f3f; 7 int f[maxn][maxn]; 8 int head[maxn],e[maxn],next[maxn],vis[maxn]; 9 int tot,n,p,ans; 10 void addedge(int u,int v) 11 { 12 e[tot]=v; 13 next[tot]=head[u]; 14 head[u]=tot++; 15 } 16 int dp(int x) 17 { 18 int i,amount=1,tem,j,k,v,coun=0; 19 f[x][1]=0; 20 for(i=head[x];i!=-1;i=next[i]) 21 { 22 coun++; 23 v=e[i]; 24 tem=dp(v); 25 amount+=tem; 26 for(j=amount-1;j>=0;j--) 27 { 28 f[x][j+1]+=f[v][0]; 29 for(k=0;k<=tem&&k<=j;k++) 30 { 31 f[x][j+1]=min(f[x][j+1],f[x][j-k+1]+f[v][k]); 32 } 33 } 34 } 35 f[x][1]=coun; 36 if(vis[x]) ans=(f[x][p]+1)<ans?(f[x][p]+1):ans; 37 else ans=f[x][p]<ans?f[x][p]:ans; 38 return amount; 39 } 40 int main() 41 { 42 cin>>n>>p; 43 int i; 44 int u,v; 45 tot=0; 46 memset(head,-1,sizeof(head)); 47 for(i=0;i<n-1;i++) 48 { 49 scanf("%d%d",&u,&v); 50 vis[v]=1; 51 addedge(u,v); 52 } 53 memset(f,inf,sizeof(f)); 54 for(i=0;i<=n;i++) f[i][0]=1; 55 for(i=1;i<=n;i++) if(!vis[i]) break; 56 ans=inf; 57 dp(i); 58 printf("%d\n",ans); 59 return 0; 60 }