二叉树动态规划：有限边容量下最大化传输数据量

刚好做过类似的二叉树网络流量优化问题，用动态规划来解简直是量身定制！我来给你一步步拆解清楚：

咱们有这么个二叉树网络：

• 所有叶子节点存着数据，每个叶子的量是s_v（非负整数）
• 每条边e都有个容量上限c_e，L_e是这条边下面子树里的所有叶子
• 目标是挑出一部分叶子节点，让最终能传到根节点r的数据总量最大，而且所有经过的边都不能超容量
• 已知c_e和s_v的最大值是m，用二叉树动态规划来搞

二叉树天生适合自底向上的动态规划——从叶子节点开始，一层一层往上算每个子树能往上传的最大数据量，同时满足路径上的边容量限制。

第一步：定义状态 #

给每个节点u（不管是叶子还是内部节点）定义一个数组dp[u]，其中dp[u][x]表示：在u的子树里选一部分叶子，通过u连向父节点的边往上传x单位数据时，子树里选的叶子总数据量的最大值。

• 这里x的范围是0 ≤ x ≤ c_e（c_e是u到父节点的边容量），如果某个x不可能实现，就用-∞标记（表示无效状态）

第二步：状态转移 #

1. 叶子节点的初始化 #

对于叶子节点v，它连到父节点的边容量是c_e：

• 如果x=0：dp[v][0] = 0（不选这个叶子，自然传0）
• 如果1 ≤ x ≤ min(c_e, s_v)：dp[v][x] = s_v（选这个叶子，最多能传s_v，但不能超边的容量c_e）
• 如果x > min(c_e, s_v)：dp[v][x] = -∞（不可能传这么多，标记无效）

2. 内部节点的状态合并 #

假设内部节点u有左孩子l和右孩子r，l到u的边容量是c_l，r到u的边容量是c_r，u到父节点的边容量是c_u。

我们要把左子树的dp[l]和右子树的dp[r]合并成u的dp[u]：
对于每个可能的x（0 ≤ x ≤ c_u），我们要找所有可能的x_l（左子树传到u的量，0 ≤ x_l ≤ c_l）和x_r（右子树传到u的量，0 ≤ x_r ≤ c_r），满足x_l + x_r = x，然后取dp[l][x_l] + dp[r][x_r]的最大值。

说白了就是：dp[u][x] = max{ dp[l][x_l] + dp[r][x_r] | x_l + x_r = x }，这有点像数组的卷积操作，只不过取的是最大值而不是求和。

3. 根节点的最终计算 #

根节点没有父节点，所以不用考虑往上传的限制，直接在dp[root]的所有有效值里找最大的那个，就是能传到根节点的最大数据总量了。

因为每个节点的状态数组长度最多是m+1（毕竟c_e最大是m），二叉树的节点数是O(n)（n是叶子数，内部节点数是n-1），每个内部节点合并状态需要O(m²)的时间（枚举左右子树的所有可能传输量组合），所以总时间复杂度是O(n*m²)，在m不大的情况下，这个效率相当不错。

比如有个小二叉树：

• 根节点r，左孩子l（边容量2），右孩子r_child（边容量3）
• 左孩子l是叶子，s_l=3；右孩子r_child是叶子，s_r=4

先初始化叶子：

• dp[l][0] = 0，dp[l][1] = 3，dp[l][2] = 3，dp[l][x>2] = -∞
• dp[r_child][0] = 0，dp[r_child][1] =4，dp[r_child][2]=4，dp[r_child][3]=4，dp[r_child][x>3] = -∞

然后合并根节点的状态（根节点没父边，所以x可以是0到2+3=5）：

• dp[root][0] = 0+0=0
• dp[root][1] = max(3+0, 0+4)=4
• dp[root][2] = max(0+4, 3+4, 3+0)=7（x_l=1，x_r=1的时候，总和是3+4=7）
• dp[root][3] = max(0+4,3+4,3+4)=7（x_l=0,x_r=3 或者 x_l=2,x_r=1）
• dp[root][4] = max(3+4,0+4)=7（x_l=2,x_r=2）
• dp[root][5] = 3+4=7（x_l=2,x_r=3）

最终最大的总量就是7，对应传5单位数据到根，完全满足左右边的容量限制（左传2，右传3）。

内容的提问来源于stack exchange，提问作者user724861