今天讲了树形dp，正好看到这道题，仔细一看，这不是板题吗（滑稽）。

咳咳，强行切入正题

首先，我们根据样例画出一张无比丑陋的图：

现在我们减去1的右枝就得到了下面这张图：

如果减去1的左枝：

如果保留1的左右枝，左子树保留条，右子树保留条，使得

由此可以推出：对于任意子树，若要保留其条枝，均可按减掉左枝，减掉右枝（剪后判断剩下的枝数是否等于）和将左右子树分为两部分（即上图红***域），分别保留和条边，使得
来进行讨论。

既然是树形dp，那就按dp的套路来分析：

首先一遍dfs建好二叉树

阶段：依次讨论以每个节点为根的子树

状态：设f[x][y]表示以x为根的子树共保留y条树枝的最大苹果数

决策：剪掉x的左枝，还是剪掉右枝，还是保留左右枝。

方程：f[x][y]=max{
                f[left[x]][y-1]+a[x][left[x]]//剪右枝
                    f[right[x]][y-1]+a[x][right[x]]//剪左枝
                    f[left[x]][k]+f[right[x]][y-2-k]+a[x][left[x]]+a[x][right[x]]//都不剪
        }

边界条件：1xn 1ym 0ky-2

时间复杂度：O(n）

但是上面方程太复杂，懒的写，所以我们换一种解决方法：

状态：设表示以为根的子树共保留个节点的最大苹果数

决策：的左右两棵子树分别保留多少个节点

方程：{ }

表示的左子树保留个节点的最优值

表示的右子树保留个节点的最优值

最后答案为:

然后其余部分同上

#include<bits/stdc++.h>
using namespace std;
int n,q,f[105][105];
int Last[105],End[205],Next[205],len[205],tot;
bool vis[105];
struct node{
    int l,r;
}tree[105];
void cb(int x,int y,int k){链式前向星
    End[++tot]=y;
    Next[tot]=Last[x];
    len[tot]=k;
    Last[x]=tot;
}
void dfs(int x){深搜建树
    vis[x]=true;标记为已经搜过
    for(int i=Last[x];i;i=Next[i]){
        int y=End[i];
        if(!vis[y]){
            if(!tree[x].l)记录儿子节点
                tree[x].l=y;
            else
                tree[x].r=y;
            f[y][1]=len[i];
            dfs(y);
        }
    }
}
int tree_dp(int x,int y){
    if(f[x][y])记忆化搜索
        return f[x][y];
    if(x==0)
        return 0;
    int maxn=0;
    for(int k=0;k<y;k++){
        int orz=tree_dp(tree[x].l,k);
        int sto=tree_dp(tree[x].r,y-k-1);
        maxn=max(maxn,orz+sto+f[x][1]);
    }
    f[x][y]=maxn;
    return f[x][y];
}
int main(){
    scanf("%d %d",&n,&q);
    for(int i=1;i<n;i++){
        int x,y,k;
        scanf("%d %d %d",&x,&y,&k);
        cb(x,y,k);
        cb(y,x,k);
    }
    dfs(1);
    printf("%d",tree_dp(1,q+1));因为是边权下放点权，所以是q+1
    return 0;
}

树形dp 小结

树形动态规划就是在“树”的数据结构上的动态规划

阶段：以每节点所代表的子树作为一个阶段。

状态：以每棵子树的最优值作为状态

决策：当前节点的最优值由其子节点代表的子树的最优值选择而来

实现：递归程序实现DP（记忆化搜索）

谢谢观看