题意：给你一棵树，n个结点，每个点有两个权值\(a_i,b_i\)，你可以选择一个结点，然后在这个结点的子树内选择一些结点，并且这些结点的\(\sum{a_i}\)小于m，则该点的贡献为\(b_i*所选结点的个数\)，求最大的贡献

题解：

可并堆（斜堆）

从根dfs，维护一个当前子树的大根堆，如果子树和大于m，就一直pop权值最大的点，然后用斜堆合并即可

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define N 100010using namespace std;int n,m,tot,e_num,nxt[N],to[N],h[N],ls[N],rs[N],rt[N],a[N],b[N],v[N];ll ans,sum[N],siz[N];int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}void add(int x, int y) { nxt[++e_num]=h[x],to[e_num]=y,h[x]=e_num;}int merge(int x, int y) { if(!x || !y) return x+y; if(v[x]
          
           m) { sum[u]-=v[rt[u]]; rt[u]=merge(ls[rt[u]],rs[rt[u]]);//注意2 siz[u]--; } ans=max(ans,siz[u]*b[u]);}int main() {//注意：所有有关堆的操作，一定是在新的编号上进行的，前期不熟练，建议把各种操作写成函数 n=gi(),m=gi(); for(int i=1; i<=n; i++) { int x=gi(); a[i]=gi(),b[i]=gi(); add(x,i); } dfs(1); printf("%lld", ans); return 0;}