以报酬为标准维护一个大根堆，从根节点往上合并，每次踢掉若干人直到花费合法后更新答案
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=100005; 6 int p[N],noww[2*N],goal[2*N],led[N]; 7 int top[N],dep[N],fth[N],siz[N],son[N][2]; 8 int n,m,t1,cnt; long long ans,val[N],cst[N]; 9 void Link(int f,int t) 10 { 11 noww[++cnt]=p[f]; 12 goal[cnt]=t,p[f]=cnt; 13 } 14 int Merge(int x,int y) 15 { 16 if(!x||!y) return x+y; 17 if(cst[x]<cst[y]) swap(x,y); 18 int &lson=son[x][0],&rson=son[x][1]; 19 rson=Merge(rson,y),fth[rson]=y; 20 if(dep[lson]<dep[rson]) swap(lson,rson); 21 dep[x]=dep[rson]+1; return x; 22 } 23 void DFS(int nde) 24 { 25 top[nde]=nde,val[nde]=cst[nde],siz[nde]=1; 26 for(int i=p[nde];i;i=noww[i]) 27 { 28 DFS(goal[i]); 29 val[nde]+=val[goal[i]]; 30 siz[nde]+=siz[goal[i]]; 31 top[nde]=Merge(top[nde],top[goal[i]]); 32 } 33 while(val[nde]>m&&siz[nde]) 34 { 35 int &tmp=top[nde]; 36 val[nde]-=cst[tmp],siz[nde]--; 37 top[nde]=Merge(son[tmp][0],son[tmp][1]); 38 } 39 ans=max(ans,1ll*siz[nde]*led[nde]); 40 } 41 int main() 42 { 43 scanf("%d%d",&n,&m); 44 for(int i=1;i<=n;i++) 45 { 46 scanf("%d",&t1); if(t1) Link(t1,i); 47 scanf("%d%d",&cst[i],&led[i]); 48 } 49 DFS(1),printf("%lld",ans); 50 return 0; 51 }