题目
题目描述
夏天近了，又到了恋爱的季节，小Q家门前的苹果树上结满了红红圆圆的苹果。
这株苹果树是一个有着$n$个结点的有根树，其中结点被依次编号为$1$至$n$。$1$号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果，第$i$个结点上有$a_i (a_i > 0)$个苹果，每取走其中一个苹果就可以得到$v_i (v_i > 0)$的幸福度（若在这个结点取走$k \leq a_i$个苹果，则可以收获$kv_i$的幸福度）。如果在一个结点取走了至少一个苹果，则必须要在其父结点处取走至少一个苹果。
现在，给定正整数$k$，请从树上取走若干苹果。如果总计取走了$t$个苹果，且所有取了至少一个苹果的那些结点的最大深度为$h$（这里规定根结点的深度为$1$），则要求$t-h \leq k$。问最大可以收获多少的幸福度？（这些幸福度全都归属于恋爱中的小Q。）
输入输出格式
输入格式：
本题有多组测试数据，输入的第一行给定整数$Q$，表示有$Q$组数据。之后依次给出$Q$组数据。
对于每一组数据来说，第一行包含两个整数$n$和$k$。
之后$n$行，每行给出三个整数，描述了每一个结点。其中第$i$行的第一个整数给出了$i$的父结点标号
（如果$i = 1$，则其父结点为$0$），第二个整数为$a_i$，第三个整数为$v_i$。
输出格式：
输出一共有$Q$行，对应了$Q$组数据。
对于每一组数据，输出一个整数，表示最大可以收获的幸福度。
输入输出样例
输入样例#1：
2
5 1
0 1 1
1 1 1
1 1 3
2 1 10
3 1 4
9 15
0 1 1
1 7 2
2 5 10
1 3 1
4 3 17
4 3 18
4 4 19
1 1 1
8 1 100
输出样例#1：
15
316
说明
有$10\%$的数据，满足$nk \leq 3000000$且给定的树的高度为$2$。
有$20\%$的数据，满足$nk \leq 25000000$且给定的树的高度为$2$。
有$20\%$的数据，满足$nk \leq 25000000$且所有$a_i$均为$1$。
还有$20\%$的数据，满足$nk \leq 3000000$，没有上述额外限制。
对于$100\%$的数据，满足$1 \leq Q \leq 5$；$1 \leq n \leq 20000$；$1 \leq k \leq 500000$；$1 \leq nk \leq 25000000$；$1 \leq a_i \leq 10^8$；$1 \leq v_i \leq 100$。
题解
首先考虑$10\%$的数据，因为树高是$2$所以可以最后讨论树根取多少，非根节点相互之间独立，所以可以做多重背包，用二进制分组优化成$O(nk\log k)$
$20\%$的数据除了$nk$大一点之外跟$10\%$没区别，考虑优化掉后面那个$\log k$，用单调队列优化多重背包即可
仔细读题，发现$t-h\le k$这个条件可以看成先选一条链，这条链上每个节点都取一个苹果（每个节点的苹果数为正），然后在树上剩下的苹果中选不超过$k$个
又发现选的链一定是某个叶子到根，因为链上选了肯定比不在链上选要优，所以最优的情况链的端点一定是叶子
这样这棵树就被分成了$3$个部分：链，链左边，链右边
$a=1$的数据就是枚举叶子（即链），然后处理出来两种后缀序求出链左/右边的$01$背包合起来即可
现在有必须选父亲再选儿子这个限制，好像混在多重背包里非常棘手，因为不知道链上的点是否还要选
发现每个节点选了大于$1$个苹果时有逻辑关系：选了$1$号苹果（指第一个，并不是真实编号）才能选$2,3,4…$号苹果
所以把苹果数大于$1$的点$x$拆开，拆出一个苹果数为$a_x-1$的叶子节点$x’$，$x’$的父亲是$x$，只有这种节点才做多重背包，原先的节点都只做$01$背包
这样就只有”必须选父亲再选儿子”这个逻辑关系了
枚举叶子，处理出两种后缀序就可以求出链左/右边的多重背包了，用单调队列优化后复杂度$O(nk)$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
# define pu(x,y) (((x)+1)*(k+1)+(y))
using namespace std;
const int N=1e6+5,MAX=6e7+5;
int n,k,Q,cnt,id,id_,ans;
int a[N],v[N],fl[N],fr[N],rel[N],rer[N],K[N],siz[N],f[MAX],g[MAX],qu[N],val[N];
vector<int> vec[N];
bool use[N];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void dfs(int x=1,int fa=0)
{
siz[x]=1,val[x]=val[fa]+v[x];
for(int i=0,cnt=vec[x].size();i<cnt;++i)
dfs(vec[x][i],x),siz[x]+=siz[vec[x][i]];
rel[fl[x]=++id]=x;
}
void dfs1(int x=1)
{
reverse(vec[x].begin(),vec[x].end());
for(int i=0,cnt=vec[x].size();i<cnt;++i)
dfs1(vec[x][i]);
rer[fr[x]=++id_]=x;
}
void Solve(int *f=f,int *re=rel)
{
for(int i=1,B,x,hl,tl;i<=cnt;++i)
{
x=re[i],B=min(k,a[x]),hl=1,tl=1,qu[1]=0,K[1]=0;
for(int j=1;j<=k;++j)
{
while(hl<=tl&&j-K[hl]>B) ++hl;
f[pu(i,j)]=max(qu[hl]+j*v[x],f[pu(i-siz[x],j)]);
while(hl<=tl&&qu[tl]<=f[pu(i-1,j)]-j*v[x]) --tl;
qu[++tl]=f[pu(i-1,j)]-v[x]*j,K[tl]=j;
}
}
}
int main()
{
Q=read();
while(Q--)
{
cnt=n=read(),k=read(),id=id_=ans=0;
memset(vec,0,sizeof(vec));
memset(use,0,sizeof(use));
for(int i=1,x;i<=n;++i)
{
x=read(),a[i]=read(),v[i]=read();
if(x) vec[x].push_back(i),use[x]=1;
if(a[i]>1) a[++cnt]=a[i]-1,a[i]=1,v[cnt]=v[i],vec[i].push_back(cnt);
}
memset(f,0,sizeof(int)*cnt*(k+1));
memset(g,0,sizeof(int)*cnt*(k+1));
dfs(),dfs1(),Solve(),Solve(g,rer);
for(int i=1;i<=n;++i)
if(!use[i]) for(int j=0;j<=k;++j)
ans=max(ans,f[pu(fl[i]-1,j)]+g[pu(fr[i]-siz[i],k-j)]+val[i]);
printf("%d\n",ans);
}
return 0;
}
