leetcode 3562

3562: 折扣价交易股票的最大利润

注：数据范围说 hierarchy.length == n - 1，且 员工 1 是所有员工的直接或间接上司，所以输入是一个 n 点 n−1 边的连通图，即树。

思路：树上背包 + 状态机 DP

寻找子问题
站在节点 x 上，讨论是否购买 present[x]。设节点 y 是节点 x 的儿子。

如果不买 present[x]，且预算至多为 j，那么问题变成：

• 从 x 的所有子树 y 中能得到的最大利润之和。
• 所有子树 y 的花费总和必须 ≤j。
• present[y] 不能半价购买。

如果买 present[x]，且预算至多为 j，那么问题变成：

• 从 x 的所有子树 y 中能得到的最大利润之和，加上买 present[x] 得到的利润。
• 买 present[x] 花了 cost，其中 cost 等于 present[x]（原价买股票）或者 ⌊present[x]/2⌋（半价买股票），取决于 x 的父节点有没有买股票。
• 所有子树 y 的花费总和必须 ≤j−cost。
• present[y] 可以半价购买。

状态设计和状态转移
dfs(x) 返回一个长为 (budget+1)×2 的二维数组 f，其中 f[j][k] 表示：

• 从子树 x 中能得到的最大利润之和。
• 预算为 j，即花费总和 ≤j。
• k=0 表示 present[x] 不能半价购买，k=1 表示 present[x] 可以半价购买。

首先，计算x 的所有儿子子树 y 的最大利润总和subF[j][k]。枚举 x 的儿子 y：

• 枚举分配给当前儿子 y 的预算 jy=0,1,2,…,j，那么分配给前面遍历过的儿子的总预算为 j−jy。
• 用前面遍历过的儿子的收益 subF[j−jy][k] 加上当前儿子 y 的收益 dfs(y)[jy][k]，更新 subF[j][k] 的最大值。注意这里用了 0-1 背包的空间优化（倒序遍历 | 至多）

然后，考虑 present[x] 是否购买，计算 f[j][k]：

• 不买 present[x]，那么分配给儿子子树的预算不变，仍然为 j，即 f[j][k]=subF[j][0]，这里的 0 是因为对于子树 y 来说，父节点 x 一定不买。
• 买 present[x]，那么分配给儿子子树的预算要扣掉 cost，即 f[j][k]=subF[j−cost][1]，这里的 1 是因为对于子树 y 来说，父节点 x 一定买。

vector<vector<int>> g(n); for(auto& e:hierarchy) g[e[0]-1].push_back(e[1]-1);

• 把输入的hierarchy转成邻接表g[x]表示x的子节点列表。
• 创建了一个长度为budget + 1的数组，每个元素是一个长度为 2 的int数组，整体可以用f[i][0]和f[i][1]来访问。

auto dfs = [&](this auto&& dfs, int x) -> vector<array<int, 2>>

• 返回一个(budget+1) × 2的表：

  • f[j][0]：父节点没买时，子树x在预算j下的最大利润。

  • f[j][1]：父节点买了时，子树x在预算j下的最大利润。

vector<array<int, 2>> sub_f(budget + 1);

• 在上司状态为 k 的条件下，只考虑 x 的所有下属（不含 x 本人），能得到的 最大净利润。

• 对每个子节点y，做分组背包：

  • 把y的子树看作一个「物品组」，体积是jy，价值是fy[jy][k]。

  • 用倒序枚举预算（类似 0-1 背包）避免重复计算。

vector<array<int, 2>> f(budget + 1);

• 再决定x自己买不买

return dfs(0)[budget][0];

• 根没有上司，相当于上司没买（k=0）；

• 取f[budget][0]即为整棵树在折扣政策下的最大净利润。

class Solution { public: int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) { //建树-下标转换 vector<vector<int>> g(n); for(auto& e:hierarchy) g[e[0]-1].push_back(e[1]-1); auto dfs=[&](this auto&& dfs,int x)->vector<array<int,2>>{ // 计算从 x 的所有儿子子树 y 中，能得到的最大利润之和（x 不买/买） vector<array<int,2>> sub_f(budget+1); for(int y:g[x]){ auto fy=dfs(y); for(int j=budget;j>=0;j--){ // 枚举子树 y 的预算为 jy //看作一个体积为 jy，价值为 fy[jy][k] 的物品 for(int jy=0;jy<=j;jy++){ for(int k=0;k<2;k++){ // k=0: x 不买，k=1: x 买 sub_f[j][k]=max(sub_f[j][k],sub_f[j-jy][k]+fy[jy][k]); } } } } // 计算从子树 x 中，能得到的最大利润之和（x 父节点不买/买） vector<array<int,2>> f(budget+1); for(int j=0;j<=budget;j++){ for(int k=0;k<2;k++){ // k=0: x 父节点不买，k=1: x 父节点买 int cost=present[x]/(k+1); if(j>=cost) f[j][k]=max(sub_f[j][0],sub_f[j-cost][1]+future[x]-cost); else{ //超过预算，只能不买 x f[j][k]=sub_f[j][0]; } } } return f; }; return dfs(0)[budget][0]; } };