二叉树上的战争决策问题 题解

问题分析

我们有一个 $n+1$ 层的完全二叉树（题目中 $n$ 表示层数减1）： 叶子节点：平民，共 $2^n$ 个 非叶子节点：贵族，包括国王 每个平民需要选择种地或参战 每个贵族需要选择后勤或打仗 贡献度条件：平民与上司事务匹配时产生贡献 约束：最多 $m$ 个平民参战

算法思路

1. 树形动态规划

使用自底向上的树形DP，状态定义为： $f[x][k]$ 表示在以节点 $x$ 为根的子树中，有 $k$ 个平民参战时能获得的最大贡献度。

2. 关键观察

对于任意节点 $x$，其决策（后勤/打仗）会影响所有后代平民对该节点的贡献。代码通过枚举祖先链状态来处理这种依赖关系。

3. 算法流程

状态转移

对于非叶子节点 $x$：

for (int i = 0; i <= siz[x<<1] && i <= k; i++)
    for (int j = 0; j <= siz[x<<1|1] && i+j <= k; j++)
        f[x][i+j] = max(f[x][i+j], f[x<<1][i] + f[x<<1|1][j]);

合并左右子树的DP结果。

祖先状态枚举

通过DFS参数 $s$ 传递祖先节点的选择状态：

void dfs(int x, int s, int dep) {
    // s 的每一位表示 x 的某个祖先的选择（0:后勤, 1:打仗）
    // 第一次DFS：所有祖先选择后勤
    dfs(x<<1, s<<1, dep+1);
    dfs(x<<1|1, s<<1, dep+1);
    // 合并结果...
    
    // 第二次DFS：当前节点选择打仗  
    dfs(x<<1, s<<1|1, dep+1);
    dfs(x<<1|1, s<<1|1, dep+1);
    // 合并结果...
}

叶子节点处理

if (dep == n+1) {  // 到达叶子
    siz[x] = 1;
    f[x][0] = f[x][1] = 0;
    
    for (int i = 0; i < dep-1; i++) {
        if (s >> i & 1)  // 第i级祖先打仗
            f[x][1] += a[x][i];  // 平民参战的贡献
        else  // 第i级祖先后勤
            f[x][0] += b[x][i];  // 平民种地的贡献
    }
    return;
}

复杂度分析

节点数：$O(2^n)$ 状态数：每个节点 $O(m)$ 状态 转移复杂度：$O(m^2)$ 合并子树 总复杂度：$O(2^n \times m^2)$，在 $n \leq 10, m \leq 512$ 时可行

样例解析

输入：

3 4  # n=2（3层树）, k=4
# 作战贡献度
503 1082
1271 369  
303 1135
749 1289
# 后勤贡献度  
100 54
837 826
947 699
216 389

处理过程： 1.构建3层完全二叉树（1个根节点，2个中间节点，4个叶子） 2.计算每个叶子在不同祖先状态下的贡献 3.自底向上DP，考虑参战平民数限制 4.最终得到最大贡献度6701

关键技巧

1.状态压缩：用整数 $s$ 的位表示祖先选择状态 2.两次DFS：分别处理当前节点选择后勤和打仗的情况 3.背包合并：用类似背包的方式合并子树DP结果 4.完全二叉树性质：利用 $2i$, $2i+1$ 的编号规则简化实现

总结

本题通过巧妙的树形DP设计，解决了完全二叉树上带约束的优化决策问题。算法充分利用了树的层次结构和状态压缩技术，在合理复杂度内求出最优解。