欢迎访谒~原文来由——博客园-zhouzhendong 去博客园看该题解 标题问题传送门 - BZOJ2809 题意归纳综合
n个点构成一棵树，，每个点都有一个带领力和用度，可以让一个点当带领，然后在这个点的子树中选择一些用度之和不赶过m的点，得到带领的带领力乘选择的点的个数（带领可不当选择）的利润。求利润最大值。n≤100000
题解做一个类似树形dp的操纵。
维护大根堆，每次从子节点到父节点就是合并所有的子节点的堆。
操作左偏树。
然后先删失大的，直到合法为止。
仿佛没什么要讲的。
代码#include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> using namespace std; typedef long long LL; const int N=100005; struct Gragh{ int cnt,y[N],nxt[N],fst[N]; void clear(){ cnt=0; memset(fst,0,sizeof fst); } void add(int a,int b){ y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt; } }g; int n,m,L[N],fa[N],C[N],root[N],cnt[N]; struct heap{ int ls,rs,v,len; void set(int a,int b,int c,int d){ ls=a,rs=b,v=c,len=d; } }h[N]; LL ans=0,tot[N]; LL max(LL a,LL b){ return a>b?a:b; } int merge(int a,int b){ if (a==0||b==0) return a+b; if (h[a].v<h[b].v) swap(a,b); h[a].rs=merge(h[a].rs,b); if (h[h[a].ls].len<h[h[a].rs].len) swap(h[a].ls,h[a].rs); h[a].len=h[h[a].rs].len+1; return a; } void dfs(int rt){ tot[rt]=C[rt],cnt[rt]=1; root[rt]=rt; h[rt].set(0,0,C[rt],0); for (int i=g.fst[rt];i;i=g.nxt[i]){ dfs(g.y[i]); root[rt]=merge(root[rt],root[g.y[i]]); tot[rt]+=tot[g.y[i]],cnt[rt]+=cnt[g.y[i]]; } while (tot[rt]>m){ tot[rt]-=h[root[rt]].v; root[rt]=merge(h[root[rt]].ls,h[root[rt]].rs); cnt[rt]--; } ans=max(ans,1LL*L[rt]*cnt[rt]); } int main(){ scanf("%d%d",&n,&m); g.clear(); for (int i=1;i<=n;i++){ scanf("%d%d%d",&fa[i],&C[i],&L[i]); g.add(fa[i],i); } dfs(1); printf("%lld",ans); return 0; }