题目链接

思路

显然，选取需要工资最少的几个人最优。

枚举领导者的编号，问题就变成了求每个点的子树中工资kk能满足多少员工了。

很容易想到使用可并堆，如果选择建立小根堆会TLE，正解是选择建立大根堆，每次从这个点的子树中踢出需要工资最大的员工，如果被一个点的子节点踢出了，那么这个节点显然不会选择他。一步一步向上合并就可以A了。

代码

#include 
    
     #include 
     
      const int maxn=100000;int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}struct node{  node* son[2];  node* fa;  int val,dist;};node tnode[maxn+10];node* root[maxn+10];int n,m,cnt,nump[maxn+10],c[maxn+10],l[maxn+10];long long giv[maxn+10],ans;int pre[maxn+10],now[maxn+10],son[maxn+10],tot;inline int upd_dist(node* now){  if(now->son[1]==NULL)    {      now->dist=0;    }  else    {      now->dist=now->son[1]->dist+1;    }  return 0;}node* merge(node* a,node* b){  if(a==NULL)    {      return b;    }  if(b==NULL)    {      return a;    }  if(a->val
      
       val)    {      std::swap(a,b);    }  a->son[1]=merge(a->son[1],b);  if(a->son[1]!=NULL)    {      a->son[1]->fa=a;    }  if((a->son[0]!=NULL)&&(a->son[1]!=NULL)&&(a->son[0]->dist
       
        son[1]->dist))    {      std::swap(a->son[0],a->son[1]);    }  else if((a->son[0]==NULL)&&(a->son[1]!=NULL))    {      a->son[0]=a->son[1];      a->son[1]=NULL;    }  upd_dist(a);  return a;}node* getf(node* now){  if(now->fa==NULL)    {      return now;    }  return getf(now->fa);}inline int getmax(node* x){  return getf(x)->val;}inline node* pop(node* x){  node* f=getf(x);  node* s=merge(f->son[0],f->son[1]);  s->fa=NULL;  return s;}inline int ins(int a,int b){  pre[++tot]=now[a];  now[a]=tot;  son[tot]=b;  return 0;}int dfs(int u){  root[u]=&tnode[++cnt];  root[u]->fa=root[u]->son[0]=root[u]->son[1]=NULL;  root[u]->val=c[u];  root[u]->dist=0;  giv[u]=c[u];  nump[u]=1;  int j=now[u];  while(j)    {      int v=son[j];      dfs(v);      root[u]=merge(root[u],root[v]);      giv[u]+=giv[v];      nump[u]+=nump[v];      j=pre[j];    }  while(giv[u]>m)    {      giv[u]-=getmax(root[u]);      --nump[u];      root[u]=pop(root[u]);    }  ans=std::max(ans,1ll*l[u]*nump[u]);  return 0;}int main(){  n=read();  m=read();  for(int i=1; i<=n; ++i)    {      int f=read();      ins(f,i);      c[i]=read();      l[i]=read();    }  dfs(1);  printf("%lld\n",ans);  return 0;}