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下的最大利润。
return dfs(0)[budget][0]; | 递归调用dfs(0)，返回一个vector<array<int, 2>>，然后取budget行、0列的值。 |
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]; } };
