题面

　　

解析

　　按照贪心策略我们想选尽量多的人，所以就会选费用少的人，那么对于每个节点可以建一棵值域线段树，父亲的线段树由他的所有儿子的线段树合并再单点修改而来，这样就可以快速查询有多少个数满足要求， 线段树上维护人数以及费用和， 考虑到值域有1e9， 而人数只有1e5，我们考虑离散化，因为每个节点都有一棵对应的线段树，所以我们动态开点，以压缩空间。那么接下来的问题就在于如何合并线段树了，我们设要把y号节点合并到x号节点内，分别考虑左右儿子，如果x有左儿子，则向下递归， 如果y号节点没有左儿子就返回， 或者如果达到L == R， 就合并信息； 如果y有左儿子而x没有，那就直接把y号节点的左儿子赋给x的左儿子，返回。右儿子的操作是一样的。

　　还有一个在合并线段树时的小优化，如果左儿子的sum已经大于m了， 就更新父亲节点的信息，不合并右儿子，直接返回，好像的确快些。

　　其余细节详见代码。

　代码：

 

#include
      
       using namespace std;typedef long long ll;const int maxn = 100005;template
       
         void read(T &re){    re=0;    T sign=1;    char tmp;    while((tmp=getchar())&&(tmp<'0'||tmp>'9')) if(tmp=='-') sign=-1;    re=tmp-'0';    while((tmp=getchar())&&(tmp>='0'&&tmp<='9')) re=(re<<3)+(re<<1)+(tmp-'0');    re*=sign;}int tot, root[maxn], n, m, w[maxn], v[maxn], mas, aw[maxn], cnt, f[maxn];ll ans;struct seg_tree{    int ls, rs, num;    ll sum;}tr[maxn * 20];void update(int x){    tr[x].num = tr[tr[x].ls].num + tr[tr[x].rs].num ;    tr[x].sum = tr[tr[x].ls].sum + tr[tr[x].rs].sum ;}void Merge(int x, int y, int L, int R){    if(!y)    return ;    if(L == R)    {        tr[x].num += tr[y].num;        tr[x].sum += tr[y].sum;        return ;    }    int mid = (L + R)>>1;    if(tr[x].ls)        Merge(tr[x].ls, tr[y].ls, L, mid);    else        tr[x].ls = tr[y].ls;    if(tr[tr[x].ls].sum > m)    {        update(x);        return ;    }        if(tr[x].rs)        Merge(tr[x].rs, tr[y].rs, mid + 1, R);    else        tr[x].rs = tr[y].rs;    update(x);}void Modify(int x, int val, int L, int R){    if(L == R)    {        tr[x].num ++;        tr[x].sum += aw[val];        return ;    }    int mid = (L + R)>>1;    if(val <= mid)    {        if(!tr[x].ls)            tr[x].ls = ++tot;        Modify(tr[x].ls, val, L, mid);    }    else    {        if(!tr[x].rs)            tr[x].rs = ++tot;        Modify(tr[x].rs, val, mid + 1, R);    }    update(x);}int Query(int x, int L, int R, ll rest){    if(rest >= tr[x].sum)        return tr[x].num;    if(L == R)        return rest / aw[L];    int mid = (L + R)>>1, ret = 0;    if(tr[x].ls && rest <= tr[tr[x].ls].sum)        ret += Query(tr[x].ls, L, mid, rest);    else if(tr[x].rs)    {        ret += tr[tr[x].ls].num ;        ret += Query(tr[x].rs, mid + 1, R, rest - tr[tr[x].ls].sum);    }        return ret;}int main(){    read(n);read(m);    for(int i = 1; i <= n; ++i)    {        root[i] = ++tot;        int x, y, z;        read(x);read(y);read(z);        f[i] = x;        aw[i] = w[i] = y;        v[i] = z;    }    sort(aw + 1, aw + n + 1);    cnt = unique(aw + 1, aw + n + 1) - aw - 1;    for(int i = n; i; --i)    {        Modify(root[i], lower_bound(aw + 1, aw + cnt + 1, w[i]) - aw, 1, cnt);        ans = max(ans, 1LL * v[i] * Query(root[i], 1, cnt, (ll)m));        if(f[i])            Merge(root[f[i]], root[i], 1, cnt);    }    printf("%lld", ans);    return 0;}