3562. 折扣价交易股票的最大利润（树上背包学习） · znzryb
## 思路讲解
【树上背包【力扣周赛 451】】 [https://www.bilibili.com/video/BV1o1jgzJE51/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37](https://www.bilibili.com/video/BV1o1jgzJE51/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37)
这个视频讲树上背包问题讲的非常透彻，非常好。
这个第一个遍历边就不多说了，第二个循环倒过来是因为滚动数组优化，第三个必须正过来，你可以倒过来试一试，当数据中含有这个需要0元，但是价值不为0的物品时就会出错，这是因为倒过来遍历可能取了这个物品两次，正过来遍历的时候是空的，那么就不存在这个问题了。
```cpp
auto dfs=[&](this auto &&self,int u,int p)->void{
for(auto v:g[u]){
if(v==p) continue;
self(v,u);
}
// memo是暂时不考虑当前节点u而定的
vector<array<int,3> > memo(budget+5,{0,0,0});
for(auto &v:g[u]){
for(int i=budget;i>=0;--i){
for(int j=0;j<=i;++j){ // 必须要正过来循环
memo[i][1]=max(memo[i][1],memo[i-j][1]+dp[1][v][j]);
memo[i][2]=max(memo[i][2],memo[i-j][2]+dp[2][v][j]);
}
}
}
for(int i=budget;i>=0;--i){
for(int j=1;j<=2;++j){
int cost=present[u-1]/j;
dp[j][u][i]=max(dp[j][u][i],memo[i][1]);
if(i>=cost){
dp[j][u][i]=max(dp[j][u][i],future[u-1]-cost+memo[i-cost][2]);
}
}
}
};
```
## AC代码
::: 源代码
```cpp
class Solution {
public:
int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) {
int dp[3][170][170];
for(int i=1;i<=2;++i){ // init
for(int j=0;j<=n+5;++j){
for(int k=0;k<=budget+5;++k){
dp[i][j][k]=0;
}
}
}
vector<vector<int> > g(n+5);
for(auto &t:hierarchy){
g[t[0]].push_back(t[1]);
}
// ism==1是父亲没买，ism==2是父亲买了
auto dfs=[&](this auto &&self,int u,int p)->void{
for(auto v:g[u]){
if(v==p) continue;
self(v,u);
}
// memo是暂时不考虑当前节点u而定的
vector<array<int,3> > memo(budget+5,{0,0,0});
for(auto &v:g[u]){
for(int i=budget;i>=0;--i){
for(int j=0;j<=i;++j){ // 必须要正过来循环
memo[i][1]=max(memo[i][1],memo[i-j][1]+dp[1][v][j]);
memo[i][2]=max(memo[i][2],memo[i-j][2]+dp[2][v][j]);
}
}
}
for(int i=budget;i>=0;--i){
for(int j=1;j<=2;++j){
int cost=present[u-1]/j;
dp[j][u][i]=max(dp[j][u][i],memo[i][1]);
if(i>=cost){
dp[j][u][i]=max(dp[j][u][i],future[u-1]-cost+memo[i-cost][2]);
}
}
}
};
dfs(1,1);
int ans=0;
for(int i=budget;i>=0;--i){
ans=max({ans,dp[1][1][i]});
}
return ans;
}
};
```
:::
## 心路历程（WA，TLE，MLE……）