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

1、

2、题目大意：

给出一棵树，该树有n个结点，每条边都有一定量的苹果，现在要删除其中的一部分分支，使得分支数为m条，求最多可以保留多少苹果。其中1号点始终是树根

分析：要想删除第i条边，那么i边的子边也将随着删除，

我们把每条边的值都保存在结点中，对于一条边有两个结点即父节点和子节点，我们把权值放到子节点中，那么根节点即1点权值是0；

保留m条边即保留m+1个结点

用dp[rt][m]表示以rt为根，保留m个子节点的最大值（如果包括rt这个根节点，那么是m+1个结点）

dp[rt][m]=max(dp[rt][m],dp[rt.left][a]+dp[rt.right][b])+tree[rt].w;

即以rt为根的最大值就等于以rt左孩子为根的a条边和加上以rt右孩子为根的b条边和，最后在加上rt自己本身

所以a+b+1=m

3、AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 205struct node{    int l;    int r;    int w;} tree[N];int v[N][N];int dp[N][N];int visit[N];void build(int rt,int n){    visit[rt]=1;    for(int i=1; i<=n; i++)    {        if(visit[i]==0 && v[rt][i]!=-1)        {            if(tree[rt].l==0)                tree[rt].l=i;            else                tree[rt].r=i;            tree[i].w=v[rt][i];            build(i,n);        }    }}int dfs(int rt,int m){    if(rt==0 || m<=0)    return dp[rt][m]=0;    if(dp[rt][m]!=-1)    return dp[rt][m];    dp[rt][m]=0;    for(int a=0;a
     
    
   

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