题目描述

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为 Master。除了 Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者 发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递 人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。写一个程序，给定每一个忍者i的上级Bi，薪水Ci，领导力L i，以及支付给*忍者们的薪水总预算M，输出在预算内满足上述要求时顾客满意度的最大值。

1 ≤N ≤ 100,000 忍者的个数；

1 ≤M ≤ 1,000,000,000 薪水总预算；

0 ≤$Bi$ < i 忍者的上级的编号；

1 ≤$Ci$ ≤ M 忍者的薪水；

解题思路

不想说什么，很明显的左偏树。

从叶子节点往根上合并，如果堆内元素和大于M就把最大的数丢掉。

1 ≤$Ci$ ≤ M 这个条件保证堆不为空真棒。

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
inline int _read(){int num=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') num=num*10+ch-48,ch=getchar();return num;
}
const int maxn=100005;
struct jz{jz* son[2];int s,w;LL x;
}*rt[maxn],t[maxn],*null=t,*len=t;
jz* newnode(int x){len++;len->x=len->w=x;len->s=1;len->son[0]=len->son[1]=null;return len;
}
int tot,son[2*maxn],nxt[2*maxn],lnk[maxn];
int n,m,L[maxn],gen;
LL ans;
void add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
jz* merge(jz* x,jz* y){if (x->w < y->w) swap(x,y);if (y==null) return x;x->son[1]=merge(x->son[1],y);if (x->son[1]->s > x->son[0]->s) swap(x->son[1],x->son[0]);x->s=x->son[0]->s + x->son[1]->s +1;x->x=x->son[0]->x + x->son[1]->x +x->w;return x;
}
void DFS(int x,int fa){for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=fa) DFS(son[j],x),rt[x]=merge(rt[x],rt[son[j]]);while(rt[x]->x >m) rt[x]=merge(rt[x]->son[1],rt[x]->son[0]);ans=max(ans,(LL)rt[x]->s*L[x]);
}
int main(){freopen("exam.in","r",stdin);freopen("exam.out","w",stdout);n=_read();m=_read();for (int i=1;i<=n;i++){int x=_read(),c=_read();L[i]=_read();if (x) add(i,x),add(x,i);else gen=i;rt[i]=newnode(c);}DFS(gen,0);printf("%lld\n",ans);return 0;
}