1575：【例 1】二叉苹果树(树形DP)

1575：【例 1】二叉苹果树
问题描述
有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共 N 个节点，标号 1 至 N，树根编号一定为 1。
我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

思路

• 分析

1. 这一题让我们 从一棵树中删除一些边，是剩余的边数为 m，其实就是从原来的那棵树上，删去一子树，使剩下的 m 条边的权值之和最大，

• 思路

2. 思路大致是：先 dfs 到叶子节点，之后从下往上的回溯过程中，对于回溯过程中遇到的节点 u，解决了以 u 为子树的问题的最优解之后，继续回溯，解决字数问题的最优解，，，，这样当我 一个一个点解决的每一子树的最优解问题之后，回溯到 根节点，就可以解决 整棵树的 最优解问题了，
3. 对于每一颗子树的最优解，假设这颗子树以 u 为根，假设 u 有 v1、v2…vx 个节点，我们可把求解子树的最优解的问题转化为背包问题的求解最优解的问题，我们可以把这些子节点，当成一个背包问题的中的物品，而 m 自然是背包的空间，当我们给每个物品分配的 空间（边数）不同的时候，这件物品的价值也会随着改变（这应该可以叫做：泛化物品 吧），对于这种物品价值随着分配空间改变的物品的解决方案就是，我们在背包的问题的两层 for 循环的基础上，在加上一层 for 循环来枚举给当前物品 v 分配的空间，
4. 那么我们就按照背包的思想来做：
5. 定义：dp [u][x]: 表示对于以 u 为根节点的子树中，如果有 x 个空间（条边）时候，能产生的最优值，
6. 第一层 for 循环枚举 背包空间 i（m>=i>=1）
7. 第二层 for 循环枚举的给 u 的子节点 vi 分配的空间设为 j (这个空间分配这个空间所能得到的最优值为：dp [v][j])，那么此时剩余的空间为 i - j，此时还要在 减去一个 1，因为如果我们要分配给 v 空间（边数），那么 u-vi 之间的边 也占用一个空间，所以最终剩余的空间为 i - j -1, 对于这个剩余的空间，所能得到的最优值为：在前 i-1 个物品（是 u 的子节点）空间为 i-j-1 的情况下所能得到的最优值是 dp [u][i - j - 1], 最后在加上 u - vi 这条的边的权值（苹果数量）w [u][vi] 就是最优解了
8. 注意????上面只有 两层 for 循环，但是在递归回溯的时候，会经过 / 遍历 u 的所有子节点，这也相当于在地第一层 for 循环的外边隐藏的一层 for 循环，而这一层 for 循环的作用是：枚举物品（子节点）
9. 所以状态转移方程为：dp [u][i] = max (dp [u][i],dp [v][j]+dp [u][j-i-1]+w [u][v])

代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
/* #include <unordered_map> */
#include <bitset>
#include <vector>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
#define ios ios::sync_with_stdio(false)
#define Pi acos(-1)
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define db double
#define Pir pair<int, int>
#define m_p make_pair
#define INF 0x3f3f3f3f
#define esp 1e-7
#define for_(i, s, e) for(int i = (ll)(s); i <= (ll)(e); i ++)
#define rep_(i, e, s) for(int i = (ll)(e); i >= (ll)(s); i --)
#define sc scanf
#define pr printf
#define sd(a) scanf("%d", &a)
#define ss(a) scanf("%s", a)
#define size() size() * 1LL
#define mod (ll)(998244353)
#define Min(a, b, c) min(a, min(b, c))
using namespace std;

const int mxn = 105;
int dp[mxn][mxn];
vector<int> e[mxn];
int w[mxn][mxn];
int n, m;

void dfs(int u, int p)
{
    if(! e[u].size()) return;
    for_(i, 0, e[u].size() - 1)
    {
        int v = e[u][i];
        if(v == p) continue;
        dfs(v, u);

        //这里的两重for循环dp枚举思路就像 01背包的动态规划，我们当前在节点u，如果我们给子节点v（把u的任意一个子节点v，在不同空间下可以看作不同的物品）分配b条边，在背包总空间为a的基础上,又因为边u-v 也占用一条边（一个空间），所以剩下的边数（空间）为 a - b - 1，
        rep_(a, m, 1)               //从大到小枚举，当前可以分配的总的边数（其实就像 从大到下枚举背包的空间，防止重复购买某个物品） 
            for_(b, 0, a - 1)
                dp[u][a] = max(dp[u][a], dp[v][b] + dp[u][a - b - 1] + w[u][v]);
    }
}


int main()
{
    /* fre(); */
    sc("%d %d", &n, &m);
    int u, v, x;
    for_(i, 2, n)
    {
        sc("%d %d %d", &u, &v, &x);
        e[u].pb(v);
        e[v].pb(u);
        w[u][v] = x;
        w[v][u] = x;
    }

    dfs(1, 0);
    pr("%d\n", dp[1][m]);

    return 0;
}

本文地址：https://blog.csdn.net/qq_34261446/article/details/109003539