在一个忍者的帮派里，一些忍者们当选中调派给顾客，然后依据本身的事情获取报偿。
Description在这个帮派里，有一名忍者被称之为Master。除了Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的带领力，所有与他们事情相关的指令总是由上级发送给他的直接部属，而不允许通过其他的方法发送。
此刻你要招募一批忍者，并把它们调派给顾客。你需要为每个被调派的忍者付出必然的薪水，同时使得付出的薪水总额不赶过你的预算。此外，为了发送指令，你需要选择一名忍者作为打点者，要求这个打点者可以向所有被调派的忍者发送指令，在发送指令时，任何忍者（不管是否被调派）都可以作为动静的通报人。打点者本身可以被调派，也可以不被调派。固然，如果打点者没有被排遣，你就不需要付出打点者的薪水。
你的方针是在预算内使顾客的对劲度最大。这里界说顾客的对劲度为调派的忍者总数乘以打点者的带领力程度，此中每个忍者的带领力程度也是必然的。
写一个措施，给定每一个忍者i的上级Bi，薪水Ci，带领力Li，以及付出给忍者们的薪水总预算M，输出在预算内满足上述要求时顾客对劲度的最大值。
Input第一行包罗两个整数N和M，此中N暗示忍者的个数，M暗示薪水的总预算。
接下来N行描述忍者们的上级、薪水以及带领力。此中的第i行包罗三个整数Bi,Ci,Li分袂暗示第i个忍者的上级，薪水以及带领力。Master满足Bi=0，并且每一个忍者的老板的编号必然小于本身的编号Bi<i。
Output输出一个数，，暗示在预算内顾客的对劲度的最大值。
Sample Input5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1
6
Hint$1 ≤ N ≤ 100,000 $忍者的个数；
$1 ≤ M ≤ 1,000,000,000 $薪水总预算；
$0 ≤ Bi < i $忍者的上级的编号；
\(1 ≤ Ci ≤ M\) 忍者的薪水；
$1 ≤ Li ≤ 1,000,000,000 $忍者的带领力程度。
对付 30%的数据，N ≤ 3000。
Solution左偏树维护最大值,权值和,子树巨细,然后每次子树内合并,最后弹出包罗该节点的左偏树中尽可能少的点,使得左偏树内权值和不赶过M,贪心即可,更新一下答案.时间庞大度\(O(n \log n)\).
Code#include <stdio.h> #include <string.h> #include <algorithm> #define MN 100005 #define R register #define ll long long #define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout) #define endfile fclose(stdin),fclose(stdout) inline int read(){ R int x; R bool f; R char c; for (f=0; (c=getchar())<‘0‘||c>‘9‘; f=c==‘-‘); for (x=c-‘0‘; (c=getchar())>=‘0‘&&c<=‘9‘; x=(x<<3)+(x<<1)+c-‘0‘); return f?-x:x; } inline ll max(ll a,ll b){return a>b?a:b;} inline int max(int a,int b){return a>b?a:b;} inline int min(int a,int b){return a<b?a:b;} inline void swap(int &a,int &b){a^=b,b^=a,a^=b;} int ch[MN][2],ht[MN],n,m,to[MN],nt[MN],h[MN],vl[MN],v[MN],sz[MN],rt,en;ll sum[MN],ans; inline void ins(int u,int v){ if (!u) return (void)(rt=v); to[++en]=v,nt[en]=h[u],h[u]=en; } inline int merge(int x,int y){ if (!x||!y) return x+y; if (vl[x]<vl[y]) swap(x,y); ch[x][1]=merge(ch[x][1],y); if (ht[ch[x][1]]>ht[ch[x][0]]) swap(ch[x][0],ch[x][1]); sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+vl[x]; ht[x]=ht[ch[x][1]]+1;return x; } inline int dfs(int u){ R int tmp=u; for (R int i=h[u]; i; i=nt[i]) tmp=merge(tmp,dfs(to[i])); while (sum[tmp]>m) tmp=merge(ch[tmp][0],ch[tmp][1]); ans=max(ans,(ll)sz[tmp]*v[u]); return tmp; } int main(){ n=read(),m=read();ht[0]=-1; for (R int i=1; i<=n; ++i) ins(read(),i),sum[i]=vl[i]=read(),v[i]=read(),sz[i]=1; dfs(rt);printf("%lld\n",ans); endfile;return 0; }