首先我们确定了领导者和派遣出去的忍着数目就确定了答案
那么我们枚举领导者，每次一定派遣薪水最少的忍者们
然后先DFS，然后每次超过m我们就在可并堆中pop掉薪水最多的忍着
因为薪水是正数，所以这样做是对的
#include<cstdio>
#include<algorithm>
using namespace std;
int n,h[100005],en,siz[100005],root[100005],cnt;
long long m,ans,sum[100005];
struct Ninja{
int b;
long long c,l;
}ninja[100005];
struct Edge{
int b,next;
}e[1000005];
struct Heap{
int l,r,dis;
long long v;
}heap[100005];
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
int Newheap(long long x){
heap[++cnt].v=x;
heap[cnt].l=heap[cnt].r=heap[cnt].dis=0;
return cnt;
}
int Merge(int A,int B){
if(!A)return B;
if(!B)return A;
if(heap[A].v<heap[B].v)swap(A,B);
heap[A].r=Merge(heap[A].r,B);
if(heap[heap[A].l].dis<heap[heap[A].r].dis)swap(heap[A].l,heap[A].r);
heap[A].dis=heap[heap[A].r].dis+1;
return A;
}
long long Top(int x){return heap[x].v;}
void Pop(int &x){x=Merge(heap[x].l,heap[x].r);}
void dfs(int u){
root[u]=Newheap(ninja[u].c);
siz[u]=1;
sum[u]=ninja[u].c;
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
dfs(v);
sum[u]+=sum[v];
siz[u]+=siz[v];
root[u]=Merge(root[u],root[v]);
}
while(sum[u]>m){
sum[u]-=Top(root[u]);
Pop(root[u]);
siz[u]--;
}
ans=max(ans,siz[u]*ninja[u].l);
}
int main(){
freopen("2809.in","r",stdin);
freopen("2809.out","w",stdout);
scanf("%d %lld",&n,&m);
heap[0].dis=-1;
for(int i=1;i<=n;i++){
scanf("%d %lld %lld",&ninja[i].b,&ninja[i].c,&ninja[i].l);
AddEdge(ninja[i].b,i);
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
评论 (0)
