本文共 747 字，大约阅读时间需要 2 分钟。

1、

2、题目大意：

已知一棵树有n个结点，现在要删除部分边，使得有一棵独立的子树上的结点个数为p个，求满足条件下，最少删除几条边

分析：

这是一道树形DP，对于第k条边来说要么删除要么不删除

dp[i][j]表示以i为根的树有j个结点的最小代价（最少删除的边数），

dp[u][j]=max(dp[u][j]+1,dp[u][j-k]+dp[v][k])

要是删除第k条边那么dp[u][j]=dp[u][j]+1,不删除第K条边就等于dp[u][j-k]+dp[v][k]

3、AC代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define N 155#define INF 0x7ffffffvector
       
         adj[N];int in[N],m,n;int dp[N][N];int tmp;void dfs(int u){    for(int i=0; i<=n; i++)        dp[u][i]=INF;    dp[u][1]=0;    for(int i=0; i
        
         =0; j--) { tmp=dp[u][j]+1; for(int k=0; k<=j; k++) { tmp=min(tmp,dp[u][j-k]+dp[v][k]); } dp[u][j]=tmp; } }}int main(){ int a,b,s; scanf("%d%d",&n,&m); memset(in,0,sizeof(in)); for(int i=1; i
        
       
      
     
    
   

转载地址：http://trddi.baihongyu.com/