枚举管理者
则一定派遣子树中薪水最低的忍者，对于每个节点维护子树大根堆
若堆中忍者薪水和大于M，则pop
#include<cstdio>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=
100002;
int cnt,n,m,root[maxn],c[maxn],ld[maxn],siz[maxn<<
2],tr[maxn<<
2][
2],b[maxn],dis[maxn<<
2],w[maxn<<
2];
ll ans=-
1,sum[maxn<<
2];
inline void read(
int &
x){
char ch=getchar();x=
0;
int f=
1;
while(!isdigit(ch)){
if(ch==
'-')f=-
1;ch=
getchar();}
while(isdigit(ch)){x=(x<<
1)+(x<<
3)+ch-
'0';ch=
getchar();}
x*=
f;
}
inline int nownode(
int x){
sum[++cnt]=x;w[cnt]=x;siz[cnt]=
1;
return cnt;
}
inline int merge(
int x,
int y){
if(!x || !y)
return x+
y;
if(w[x]<
w[y])swap(x,y);
tr[x][1]=merge(tr[x][
1],y);
siz[x]=siz[tr[x][
0]]+siz[tr[x][
1]]+
1;
sum[x]=sum[tr[x][
0]]+sum[tr[x][
1]]+
w[x];
if(dis[tr[x][
0]]<dis[tr[x][
1]])swap(tr[x][
0],tr[x][
1]);
dis[x]=dis[tr[x][
1]]+
1;
return x;
}
int main(){
read(n);read(m);
for(
int i=
1;i<=n;i++){read(b[i]);read(c[i]);read(ld[i]);root[i]=
nownode(c[i]);}
for(
int i=n;i>
0;i--
){
while(sum[root[i]]>m)root[i]=merge(tr[root[i]][
0],tr[root[i]][
1]);
ans=max(ans,1LL*ld[i]*
siz[root[i]]);
if(b[i])root[b[i]]=
merge(root[i],root[b[i]]);
}
printf("%lld",ans);
return 0;
}
转载于:https://www.cnblogs.com/MikuKnight/p/9206043.html
相关资源：JAVA上百实例源码以及开源项目
