点击这里查看原题
对于每个忍者被作为管理者的情况，我们需要知道这个忍者管理的忍者中最多能选多少忍者，而要使选的忍者尽可能多，就需要从薪水最低的忍者开始选。 于是可以建立一颗权值线段树，按DFS序将忍者的薪水依次加入，每次求总薪水小于等于k可以选多少忍者。 注意long long，因为这个WA了好几次
/* User:Small Language:C++ Problem No.:2809 */ #include<bits/stdc++.h> #define ll long long using namespace std; const int M=1e5+5; int n,rt[M],tot,fir[M],cnt,in[M],out[M],dfn,a[M],p[M],id[M],pos[M],ls[M*20],rs[M*20],val[M]; ll sum[M*20],sz[M*20],ans,k,b[M]; struct edge{ int v,nex; }e[M<<1]; void add(int u,int v){ e[++tot]=(edge){v,fir[u]}; fir[u]=tot; } bool cmp(int x,int y){ return a[x]<a[y]; } void dfs(int u){ in[u]=++dfn; id[dfn]=pos[u]; val[dfn]=a[u]; for(int i=fir[u];i;i=e[i].nex) dfs(e[i].v); out[u]=dfn; } void build(int &now,int l,int r,int x,int v){ cnt++; sum[cnt]=(ll)sum[now]+(ll)v; sz[cnt]=sz[now]+1; ls[cnt]=ls[now]; rs[cnt]=rs[now]; now=cnt; if(l==r) return; int mid=l+r>>1; if(x<=mid) build(ls[now],l,mid,x,v); else build(rs[now],mid+1,r,x,v); } ll query(int a,int b,int l,int r,ll k,ll c){ int mid=l+r>>1; if(l==r){ if(sum[b]-sum[a]<=k&&sum[b]-sum[a]) return c+1; else return c; } ll t=sum[ls[b]]-sum[ls[a]]; if(t>=k) return query(ls[a],ls[b],l,mid,k,c); else{ return query(rs[a],rs[b],mid+1,r,k-t,c+sz[ls[b]]-sz[ls[a]]); } } int main(){ freopen("data.in","r",stdin);// scanf("%d%lld",&n,&k); for(int i=1;i<=n;i++){ int fa; scanf("%d%d%lld",&fa,&a[i],&b[i]); if(fa) add(fa,i); p[i]=i; } sort(p+1,p+n+1,cmp); for(int i=1;i<=n;i++) pos[p[i]]=i; dfs(1); for(int i=1;i<=n;i++){ rt[i]=rt[i-1]; build(rt[i],1,n,id[i],val[i]); } for(int i=1;i<=n;i++){ ll res=query(rt[in[i]-1],rt[out[i]],1,n,k,0); ans=max(ans,(ll)res*b[i]); } printf("%lld\n",ans); return 0; }另一种做法是可并堆，维护最大堆，每当堆中的元素和大于总薪水时删除最大元素。
/* User:Small Language:C++ Problem No.:2809 */ #include<bits/stdc++.h> #define ll long long using namespace std; const int M=1e5+5; ll n,tot,fir[M],siz[M],rt[M]; ll m,sum[M],b[M],ans,a[M]; struct edge{ ll v,nex; }e[M<<1]; struct no{ ll l,r; ll v; }tr[M<<2]; void add(ll u,ll v){ e[++tot]=(edge){v,fir[u]}; fir[u]=tot; } ll merge(ll a,ll b){ if(!a||!b) return a+b; if(tr[a].v<tr[b].v) swap(a,b); tr[a].r=merge(tr[a].r,b); swap(tr[a].l,tr[a].r); return a; } void pop(ll x){ ll root=rt[x]; rt[x]=merge(tr[root].l,tr[root].r); sum[x]-=tr[root].v; siz[x]--; tr[root].l=tr[root].r=tr[root].v=0; } void dfs(ll u){ for(ll i=fir[u];i;i=e[i].nex){ ll v=e[i].v; dfs(v); sum[u]+=sum[v]; siz[u]+=siz[v]; rt[u]=merge(rt[u],rt[v]); while(sum[u]>m) pop(u); } sum[u]+=a[u]; siz[u]++; tr[u]=(no){0,0,a[u]}; rt[u]=merge(rt[u],u); while(sum[u]>m) pop(u); ans=max(ans,(ll)siz[u]*b[u]); } int main(){ freopen("data.in","r",stdin);// scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++){ ll fa; scanf("%lld%lld%lld",&fa,&a[i],&b[i]); if(fa) add(fa,i); } dfs(1); printf("%lld\n",ans); return 0; }