二叉苹果树

1 题意

题目:luogu P2015: 二叉苹果树。

一棵以 11 为根的二叉树,每条边上有一定数量的苹果。要求恰好保留 QQ 条边,保留下来的部分必须与根连通,求最多能保留多少苹果。

原题中 1≤Q<N≤1001\le Q<N\le100,每条边上的苹果数不超过 3000030000。

不能直接挑最大的 QQ 个边权。保留一条深处的边,必须同时保留根到它的路径。选择某个孩子子树中的内容,需要先接通通向这个孩子的边。

2 边权转点权

沿用旧文的处理方法:将每条边的权值转移到它的孩子节点上。记转移后的点权为 aua_u,根的点权为 00。

左图边权分别为 1、10、20、20,右图将每条边的权值转移到孩子节点,根点权为 0

连通的树中,边数比点数少 11。因此,保留包含根的 QQ 条边,等价于选择包含根的 Q+1Q+1 个连通节点。每个非根节点恰好对应一条保留的父边,点权之和就是苹果总数。

转换后,不能只选择后代而不选择它的祖先。否则既不连通,也会把尚未接通的父边权计入答案。

3 状态定义

定义 f[u][j]f[u][j] 为:在 uu 的子树中恰好选择 jj 个节点,所选部分连通且包含 uu 时,最大的点权和。

另外规定 f[u][0]=0f[u][0]=0,专门表示整棵子树都不取。这是空方案,不要求包含 uu。

初始只处理 uu 自己:

f[u][0]=0,f[u][1]=au. f[u][0]=0,\qquad f[u][1]=a_u.

其他状态为 −∞-\infty,表示当前无法选择这么多个节点。题目要求恰好选择,不能把所有状态初始化为 00,否则会混入数量不足的方案。

4 分配名额

如果 uu 的左右孩子是 l,rl,r,选择 j≥1j\ge1 个节点时,先给 uu 自己一个名额,再分配剩余的 j−1j-1 个:

f[u][j]=au+max⁡x+y=j−1(f[l][x]+f[r][y]). f[u][j]=a_u+\max_{x+y=j-1}\bigl(f[l][x]+f[r][y]\bigr).

这里必须检查 x,yx,y 是否可行。某个孩子分到 00 个名额,表示整个孩子子树都不取;正数名额对应的方案必须包含孩子节点。

不同孩子如何分配名额,会影响最终收益。这就是树形背包:不再只给每个孩子取一个最优值,而是保留各个选择数量下的最优值,再枚举数量分配。

5 逐个合并

代码不必专门存左右孩子,可以将孩子逐个合并。这种写法也适用于孩子数量不限的树。

合并孩子 vv 前,f[u][a]f[u][a] 表示从 uu 和之前处理过的孩子中选择 aa 个节点的最优值。当前孩子子树中选择 bb 个节点,转移为:

next[a+b]=max⁡(next[a+b],f[u][a]+f[v][b]). next[a+b]=\max\bigl(next[a+b],f[u][a]+f[v][b]\bigr).

枚举时要求 a≥1a\ge1、b≥0b\ge0、a+b≤Q+1a+b\le Q+1。其中 a≥1a\ge1 保证 uu 已选;若 b>0b>0,孩子 vv 也已选,两个连通部分通过边 (u,v)(u,v) 接通。

每个孩子都用一份清空后的 next 数组接收结果,合并完成再覆盖 f[u]f[u]。这使每棵孩子子树只参与一次,不会把同一份内容重复选入。

用 sz[u]sz[u] 记录已经合并的部分有多少节点,sz[v]sz[v] 记录当前孩子子树的大小,将枚举限制为:

1≤a≤min⁡(sz[u],Q+1),0≤b≤min⁡(sz[v],Q+1−a). 1\le a\le\min(sz[u],Q+1),\qquad 0\le b\le\min(sz[v],Q+1-a).

sz[u] 要在合并完成后增加,不能提前把当前孩子算入旧状态的规模。

6 手算示例

图中的树包含边 (1,3,1)(1,3,1)、(1,4,10)(1,4,10)、(3,2,20)(3,2,20)、(3,5,20)(3,5,20),每组三个数分别表示两端点和边权。以下取 Q=2Q=2,即恰好保留 33 个节点。

子树根 f[u][0]f[u][0] f[u][1]f[u][1] f[u][2]f[u][2] f[u][3]f[u][3]
2 0 20 −∞-\infty −∞-\infty
5 0 20 −∞-\infty −∞-\infty
3 0 1 21 41
4 0 10 −∞-\infty −∞-\infty
1 0 0 10 21

根选择 33 个节点,剩余两个名额有两种有效分配:

  • 全部分给节点 33 的子树,得到 0+21=210+21=21。
  • 两棵孩子子树各分一个,得到 0+1+10=110+1+10=11。

所以答案为 2121,保留边 (1,3)(1,3) 与 (3,2)(3,2),也可以把后一条换成 (3,5)(3,5)。

虽然 f[3][3]=41f[3][3]=41 更大,但再加上根就需要 44 个节点,超过本题名额。不能直接拿孩子子树的最大值作为答案。

7 正确性

考虑一次孩子合并。任意合法的非空选择,限制在旧部分和当前孩子子树后,分别得到大小为 a,ba,b 的方案。旧部分包含 uu;当前孩子子树若非空,就必须包含 vv,所以转移枚举覆盖了所有可能的拆分。

反过来,任意两个满足条件的子方案,都能通过父子边接成一个合法连通方案,数量和收益分别相加。按选择总数取最大值,就得到合并后的最优状态。

逐个合并全部孩子后,f[u]f[u] 符合定义。最终根的答案为 f[1][Q+1]f[1][Q+1]。

8 代码实现

dfs(u, fa, value) 中的 value 是父边转移到 uu 上的权值。对子树合并时不再额外加边权,避免重复计算。根调用时传入 00。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100 + 5;
const int NEG = -1000000000;

struct Edge {
    int to, w;
};

vector<Edge> g[maxn];
int f[maxn][maxn], sz[maxn];
int n, q, K;

void dfs(int u, int fa, int value) {
    for (int j = 0; j <= K; ++j) f[u][j] = NEG;
    f[u][0] = 0;      // 整棵子树都不取
    f[u][1] = value;  // 只取 u;value 是父边转移到 u 上的点权
    sz[u] = 1;
    int next[maxn];

    for (auto [v, w] : g[u]) {
        if (v == fa) continue;
        dfs(v, u, w);
        fill(next, next + K + 1, NEG);

        // a 个点来自 u 和之前合并的孩子,必须包含 u。
        for (int a = 1; a <= min(sz[u], K); ++a) {
            if (f[u][a] == NEG) continue;
            // b=0 表示不取当前孩子子树;b>0 时必须包含 v。
            for (int b = 0; b <= min(sz[v], K - a); ++b) {
                if (f[v][b] == NEG) continue;
                next[a + b] = max(next[a + b], f[u][a] + f[v][b]);
            }
        }
        for (int j = 1; j <= K; ++j) f[u][j] = next[j];
        sz[u] += sz[v];  // 合并完成后再扩大已处理部分的规模
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    K = q + 1;  // 保留 q 条边,等价于保留包含根的 q+1 个点
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    dfs(1, 0, 0);  // 根没有父边,转移后的点权为 0
    cout << f[1][K] << '\n';
    return 0;
}

按每次合并枚举两个数量,可先得到时间上界 O(nQ2)O(nQ^2),空间复杂度为 O(nQ)O(nQ)。原题规模下已经足够;子树大小限制还能给出更紧的时间界,下一篇《选课》会单独分析。

苹果总数不超过 99×3000099\times30000,使用 int 即可。代码在相加前检查不可行状态。

9 相关题解

暂无相关题解