题解：P3780 [SDOI2017] 苹果树
xzy_AK_IOI
·
·
题解
很深刻啊。
思路分析
说一种不要 dfs 序的做法。
首先考虑除掉 h 的限制，则其变为树上多重背包板题，考虑设 f_{u,i} 为点 u 里取了 i 个物品的最大价值，考虑转移，固然可以直接两子树做合并，但其无法套路的使用单调队列优化。
考虑一种新型的转移，具体地，在 u 这里枚举子节点 v，然后将 f_v 整体赋值为 f_u，然后递归进 v，再加入 a_v 和 V_v，但是这里插入的最大数量应不超过 a_v-1，回溯时强制加入一个 v，再更新 f_u 的值，这样可以保证 v 一定被取一个，从而其子树的要求均可被满足。
而 v 子树完全不取的情况只需要 f_{u,i}=\max(f_{u,i},V_v+f_{v,i-1}) 即可，第一项就是不取，发现其可以用单调队列优化，复杂度 \mathcal{O}(nk)。
考虑加入限制，发现其相当于先选一条链，并且无需花费任何的代价，只是 a_u\leftarrow a_u-1，可以发现那条链一定会延伸到叶子节点。
尝试探求刚刚那个算法的形态，可以发现当你处理到一个叶子节点并且做完插入时，你这一条链的所有节点都被决策插入了 a_u-1 个物品，刚好满足我们所需要的，于是再设一个 g_{u,i}，其为考虑到点 u，其到根路径上所有点均不取，且已经取了 i 个的最大权值，则答案为 \max\{f_{u,i}+g_{u,i}+W_u\}，W_u 为根到 u 路径上所有点的 V_u 和。
所以总复杂度也是 $\mathcal{O}(nk)$。
#### 完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define lli long long
#define db long double
#define ull unsigned long long
#define F(i,k,n) for (int i=k;i<=n;i++)
#define R(i,k,n) for (int i=k;i>=n;i--)
#define pu push_back
#define mpr make_pair
#define lowb(x) (x&(-x))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mes(a,b) memset(a,b,sizeof a)
#define G(a,b) ((a-1)*(k+1)+b)
#define ui unsigned int
const int N=2e4+10;
const int K=5e5+10;
const int NK=3e7+10;
const int inf=1e18;
int t,n,k,b;
int f[NK],g[NK];
int a[N],V[N],sw[N];
vector<int>T[N];
int head,tail;
int ans=0;
int st[NK];
void dfs(int u){
int zhi=k;
head=0,tail=1;
R(i,k,1){
while (head>=tail && st[tail]>i) tail++;
while (zhi>=max(0,i-a[u]+1)){
while (head>=tail && f[G(u,zhi)]-V[u]*zhi>f[G(u,st[head])]-V[u]*st[head]){
head--;
}
head++;
st[head]=zhi;
zhi--;
}
if (head>=tail) f[G(u,i)]=max(f[G(u,i)],f[G(u,st[tail])]+V[u]*(i-st[tail]));
}
F(i,0,(int)T[u].size()-1){
int v=T[u][i];
F(j,0,k) f[G(v,j)]=f[G(u,j)];
sw[v]=sw[u]+V[v];
dfs(v);
F(j,1,k){
f[G(u,j)]=max(f[G(u,j)],f[G(v,j-1)]+V[v]);
}
}
}
void dfs2(int u){
F(i,0,(int)T[u].size()-1){
int v=T[u][i];
F(j,0,k) g[G(v,j)]=g[G(u,j)];
dfs2(v);
F(j,1,k){
g[G(u,j)]=max(g[G(u,j)],g[G(v,j-1)]+V[v]);
}
}
if ((int)T[u].size()==0){
F(j,0,k){
ans=max(ans,f[G(u,j)]+g[G(u,k-j)]+sw[u]);
}
}
int zhi=k;
head=0,tail=1;
R(i,k,1){
while (head>=tail && st[tail]>i) tail++;
while (zhi>=max(0,i-a[u]+1)){
while (head>=tail && g[G(u,zhi)]-V[u]*zhi>g[G(u,st[head])]-V[u]*st[head]){
head--;
}
head++;
st[head]=zhi;
zhi--;
}
if (head>=tail) g[G(u,i)]=max(g[G(u,i)],g[G(u,st[tail])]+V[u]*(i-st[tail]));
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while (t--){
cin>>n>>k;
F(i,1,n) F(j,0,k) f[G(i,j)]=g[G(i,j)]=0;
F(i,1,n) T[i].clear();
F(i,1,n){
sw[i]=0;
cin>>b>>a[i]>>V[i];
if (b) T[b].pu(i);
}
sw[1]=V[1];
dfs(1);
F(i,1,n) reverse(T[i].begin(),T[i].end());
ans=0;
dfs2(1);
cout<<ans<<'\n';
}
return 0;
}
```