题面:

设f[u][i]表示u的子树上保留i条边，至多保留的苹果数目那么状态转移方程也就显而易见了:f[u][i]=max(f[u][i],f[u][i−j−1]+f[v][j]+e[i].w)( 1≤i≤min(q,sz[u]),0≤j≤min(sz[v],i−1))u表示当前节点，v是u的一个子节点，sz[u]表示u的子树上的边数，q就是题目中要求的最多保留边数。Code:#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int N=105;vector
            
             a[N];int n,q,f[N][N],val[N][N];bool vis[N];void dfs(int u){ if(!vis[u]){ vis[u]=1; } int length=a[u].size(); for(int i=0;i
             
              =1;j--){ for(int k=j-1;k>=0;k--){ f[u][j]=max(f[u][j],val[u][v]+f[v][k]+f[u][j-k-1]); } } } }}int main(){ int u,v,w; scanf("%d%d",&n,&q); for(int i=1;i