很久以前看到没深想
今天想做可并堆的练手题顺着标签找到这题
发现本题还算不是很难...

Problem

在这个帮派里，有一名忍者被称之为 Master。除了 Master 以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。

现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，你就不需要支付管理者的薪水。

你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。

写一个程序，给定每一个忍者 i 的上级 Bi，薪水 Ci，领导力 Li，以及支付给忍者们的薪水总预算 M，输出在预算内满足上述要求时顾客满意度的最大值。

Solution

如果确定了一个上级，那么它能招募的人也就确定了。枚举上级，我们所需要做的就是使招募的人尽量多。

维护一个可并大根堆维护薪水最大值，递归往下枚举上级。

复杂度 $O(n\log n)$。

有趣的是我一开始以为上级是必须选的

如果搞可并对顶堆的话，复杂度不好保证

考虑优化，上面要耗的钱比下面的少的话下面做上级就肯定亏了

所以从下面往上走耗的钱肯定越来越多

于是限制具有单调性，就不需要对顶堆了

到最后才发现题目理解错了，还用了很傻比的写法 233

Code

// Code by ajcxsu
// Problem: ninja

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+10, M=2e5+10;

int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) {
    nexp[p]=h[a], h[a]=p, to[p]=b, p++;
}

struct Node *nil;
struct Node {
    ll val, tot, siz;
    Node *ls, *rs;
    Node(ll val=0x3f3f3f3f3f3f3fll): val(val), tot(val) { ls=rs=nil; siz=1; }
} ;
void ini() {
    nil=new Node();
    nil->ls=nil->rs=nil, nil->siz=0;
}

Node* merge(Node *x, Node *y) {
    if(x==nil) return y;
    if(y==nil) return x;
    if(x->val < y->val) swap(x, y);
    y->rs=x->ls, x->ls=y;
    x->tot+=y->tot, x->siz+=y->siz;
    return x;
}

Node* merges(Node *x) {
    if(x==nil || x->rs==nil) return x;
    Node *a=x->rs, *b=a->rs;
    x->rs=a->rs=nil;
    return merge(merge(x, a), merges(b));
}

Node* del(Node *x) {
    Node *y=merges(x->ls);
    y->tot=x->tot-x->val;
    y->siz=x->siz-1;
    return y;
}

inline void gn(int &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int n,m;
int w[N], c[N];
ll ans=0;

Node* dfs(int x) {
    Node *nd=new Node(c[x]);
    for(int u=h[x];u;u=nexp[u])
        nd=merge(nd, dfs(to[u]));
    while(nd->tot>m) {
        nd=del(nd);
    }
    ans=max(ans, 1ll*nd->siz*w[x]);
    return nd;
}

int main() {
    ini();
    gn(n), gn(m);
    int fa, root;
    for(int i=1;i<=n;i++) {
        gn(fa), gn(c[i]), gn(w[i]);
        if(!fa) root=i;
        else ins(fa, i);
    }
    dfs(root);
    printf("%lld\n", ans);
    return 0;
}