二叉苹果树

树形dp 有依赖的背包问题

题目描述

#10153. 「一本通 5.2 例 1」二叉苹果树 - 题目 - LibreOJ (loj.ac) 有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共 $N$ 个节点，标号 $1$ 至 $N$，树根编号一定为 $1$。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

输入格式

第一行两个数 $N$ 和 $Q$ ，$N$ 表示树的节点数，$Q$ 表示要保留的树枝数量。

接下来 $N-1$ 行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。

输出格式

输出仅一行，表示最多能留住的苹果的数量。

案例

input

5 2
1 3 1
1 4 10
2 3 20
3 5 20

output

21

数据范围

对于 $100\%$ 的数据，$1\le Q\le N\le 100,N\ne 1$，每根树枝上苹果不超过 $30000$ 个。

思路

需要在树中找到包含根节点且长度为Q的一条路径, 其包含的苹果数量最大 且根据剪枝的性质, 如果当前树枝需要保留, 那么其父节点的树枝也一定需要保留, 也就是说存在依赖性。 把树枝权重放到点上, 树枝数量当做背包容量, 每个物品重量为1, 可以转化为背包问题中的有依赖背包问题。复杂度为$O(n\ast Q^2)$ 可以通过。

状态表示：f[i][j] 以i为根的节点的子树中选择j个树枝 对于i根下的子节点 S1, S2, 把每个子节点根据分配的可选树枝数量划分 即S1可以划分为： S2可以划分为： 因此在求f[i][j]时, 可以从子树中的所有状态转移过来 需要三层循环, 第一次i循环子节点, 第二次j循环当前i节点的体积, 第三次k循环分配给子节点的体积。

代码

const int N = 110, M = N * 2;
int h[N], e[M], ne[M], w[M], idx;
int n, Q;
int f[N][N];
 
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
 
void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int t = e[i];
        if (t == fa)
            continue;
        dfs(t, u);
        for (int j = Q; j >= 0; j--)
            for (int k = 0; k < j; k++)
                f[u][j] = max(f[u][j], f[t][k] + f[u][j - k - 1] + w[i]);
    }
}
 
int main()
{
    cin >> n >> Q;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
 
    dfs(1, -1);
    cout << f[1][Q] << endl;
 
    return 0;
}