考虑维护每一个点以及它的子树中被派遣的忍者。
对于一个点,我们用类似树形DP的方式自底向上进行,先把它的所有孩子中被派遣的忍者放到一起,如果他们的薪水总和超过\(m\),就不停地将其中薪水最大的忍者删除,直到薪水总和小于等于\(m\)。
找到所有点中领导能力和被派遣忍者数量乘积的最大值即可。
即维护数据结构,支持合并,删除和求最大值。
就是维护可并堆。
可以使用左偏树。
#include<bits/stdc++.h>
using namespace std;
struct Ltree{
int v,d,f,c[2];
}t[100010];
int n,m,b[100010],c[100010],l[100010],f[100010];
long long ans,num[100010],sum[100010];
vector<int>e[100010];
int Merge(int &x,int &y){
if(!y)return x;
if(!x){
swap(x,y);
return x;
}
if(t[x].v<t[y].v)swap(x,y);
Merge(t[x].c[1],y);
t[t[x].c[1]].f=x;
if(t[t[x].c[0]].d<t[t[x].c[1]].d)swap(t[x].c[0],t[x].c[1]);
t[x].d=t[t[x].c[1]].d+1;
return x;
}
int Delete(int x){
t[t[x].c[0]].f=t[t[x].c[1]].f=0;
return Merge(t[x].c[0],t[x].c[1]);
}
void TDP(int x){
for(int i=0;i<e[x].size();i++){
if(e[x][i]!=b[x]){
TDP(e[x][i]);
if(f[e[x][i]]){
num[x]+=num[e[x][i]];
sum[x]+=sum[e[x][i]];
f[x]=Merge(f[x],f[e[x][i]]);
}
}
}
while(sum[x]>m){
sum[x]-=t[f[x]].v;
num[x]--;
f[x]=Delete(f[x]);
}
ans=max(ans,num[x]*l[x]);
}
int main(){
scanf("%d%d",&n,&m);
t[0].d=-1;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&b[i],&c[i],&l[i]);
f[i]=i;
e[b[i]].push_back(i);
t[i].v=c[i];
t[i].d=0;
num[i]=1;
sum[i]=c[i];
}
TDP(1);
printf("%lld",ans);
return 0;
}