链接

思路

忍者数量肯定越多越好

那就从下到上的合并它的孩子

左偏树的话

顺便维护一个tot，大头堆，如果tot大于了m，把大的删掉

如果左偏树忘干净了或者没学的话

线段树合并也是个不错的选择

直接权值线段树合并就好，内存30倍会炸，也许是我没离散化的缘故吧

查询在线段树上面二分

左偏树代码

#include 
    
     #define FOR(i,a,b) for(int i=a;i<=b;++i)#define ll long longusing namespace std;const int maxn=100047;inline int read() {    int x=0,f=1;char s=getchar();    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';    return x*f;}struct edge {    int v,nxt;}e[maxn];int head[maxn],tot;void add_edge(int u,int v) {    e[++tot].v=v;e[tot].nxt=head[u];head[u]=tot;}int n,m,mone;ll sum[maxn],ans;int size[maxn];int ch[maxn][2],dis[maxn],val[maxn],xs[maxn];int work(int a,int b) {    if(!a||!b) return a+b;    if(val[a]
     
      mone) rt=delet(rt);    ans=max(ans,xs[u]*(ll)size[rt]);    return rt;}int main() {    n=read(),mone=read();    int root;    FOR(i,1,n) {        int x=read();        val[i]=read();xs[i]=read();        sum[i]=val[i];size[i]=1;        if(x) add_edge(x,i);        else root=i;    }    int wuyong=dfs(root);    cout<
      
       <<"\n";    return 0;}
      
     
    

线段树合并代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define ll long longusing namespace std;const int N=1e5+7;int read() {    int x=0,f=1;char s=getchar();    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';    return x*f;}int n,m,money[N],leader[N],rt[N];vector
         
           G[N];struct node { int l,r,siz; ll tot;}e[N*30];void pushup(int rt) { e[rt].siz=e[e[rt].l].siz+e[e[rt].r].siz; e[rt].tot=e[e[rt].l].tot+e[e[rt].r].tot;}int cnt;void insert(int l,int r,int L,int &rt) { rt=++cnt; if(l==r) { e[rt].siz++; e[rt].tot+=l; return; } int mid=(l+r)>>1; if(L<=mid) insert(l,mid,L,e[rt].l); else insert(mid+1,r,L,e[rt].r); pushup(rt);}int merge(int l,int r,int x,int y) { if(!x||!y) return x+y; if(l==r) { e[x].siz+=e[y].siz; e[x].tot+=e[y].tot; return x; } int mid=(l+r)>>1; e[x].l=merge(l,mid,e[x].l,e[y].l); e[x].r=merge(mid+1,r,e[x].r,e[y].r); pushup(x); return x;}int query(int l,int r,int k,int rt) { if(l==r) return k>=e[rt].tot ? e[rt].siz : 0; int mid=(l+r)>>1; if(e[e[rt].l].tot>=k) return query(l,mid,k,e[rt].l); else return e[e[rt].l].siz+query(mid+1,r,k-e[e[rt].l].tot,e[rt].r);}ll ans;void dfs(int u) { insert(1,1000000000,money[u],rt[u]); for(vector
          
           ::iterator it=G[u].begin();it!=G[u].end();++it) { dfs(*it); rt[u]=merge(1,1000000000,rt[u],rt[*it]); } ans=max(ans,(ll)leader[u]*query(1,1000000000,m,rt[u]));}int main() { n=read(),m=read(); for(int i=1;i<=n;++i) { int x=read(); money[i]=read(); leader[i]=read(); G[x].push_back(i); } dfs(1); printf("%lld",ans); return 0;}