原题链接

题目描述

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

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

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

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

输入格式

第一行包含两个整数N和M，其中N表示忍者的个数，M表示薪水的总预算。

接下来N行描述忍者们的上级、薪水以及领导力。其中的第i行包含三个整数Bi,Ci,Li分别表示第i个忍者的上级，薪水以及领导力。Master满足Bi=0，并且每一个忍者的老板的编号一定小于自己的编号Bi<i。

输出格式

输出一个数，表示在预算内顾客的满意度的最大值。

题目分析

首先对于子树的节点用权值线段树维护，线段树维护sz和sum，query询问子树中权值和不大于m最多的点（贪心取即可），然后计算答案。每次算完子节点将子节点信息合并继续更新答案。

线段树合并的时空复杂度为$O(nlogN)$
离散化既能保证时间复杂度也能保证空间复杂度

代码

#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=100010;
int h[N],e[N],ne[N],idx;
int M;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int n,m;
int c[N],l[N];
vector<int> mpc;
int find(int x)
{
    return lower_bound(mpc.begin(),mpc.end(),x)-mpc.begin();
}
struct node
{
    int l,r;
    int sz;
    ll sum;
}tree[N*40];
int root[N],cnt;
void insert(int &u,int l,int r,int p)
{
    if(!u) u=++cnt;
    tree[u].sum+=mpc[p];
    tree[u].sz++;
    if(l==r) return;
    int mid=l+r>>1;
    if(p<=mid) insert(tree[u].l,l,mid,p);
    else insert(tree[u].r,mid+1,r,p);
}
int query(int u,int l,int r,int m)
{
    if(!u) return 0;
    if(tree[u].sum<=m) return tree[u].sz;
    if(l==r)
        return min(tree[u].sz,m/mpc[l]);
    int mid=l+r>>1;
    if(tree[tree[u].l].sum>=m) return query(tree[u].l,l,mid,m);
    else return tree[tree[u].l].sz+query(tree[u].r,mid+1,r,m-tree[tree[u].l].sum);
}
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    tree[x].sz+=tree[y].sz;
    tree[x].sum+=tree[y].sum;
    tree[x].l=merge(tree[x].l,tree[y].l);
    tree[x].r=merge(tree[x].r,tree[y].r);
    return x;
}
ll res=0;
void dfs(int u)
{
    insert(root[u],0,M,find(c[u]));
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        root[u]=merge(root[u],root[j]);
    }
    res=max(res,1ll*query(root[u],0,M,m)*l[u]);
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int now;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>p>>c[i]>>l[i];
        if(p) add(p,i);
        else now=i;
        mpc.push_back(c[i]);
    }
    sort(mpc.begin(),mpc.end());
    mpc.erase(unique(mpc.begin(),mpc.end()),mpc.end());
    M=mpc.size()-1;
    dfs(now);
    cout<<res<<endl;
    return 0;
}