题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2809
思路有点暴力和贪心，就是 dfs 枚举每个点作为管理者；
当然它的子树中派遣出去的忍者越多越好，只要不超过预算；
所以需要能够合并子树情况的、能反映最大值节点的数据结构，也就是左偏树(可并堆)；
所以对于每个点维护一个大根左偏树，当子树内总和超过预算时，就去掉大根堆堆顶，这样最优；
自己的第一棵左偏树！没想到相当简单呢。
左偏树的论文：https://wenku.baidu.com/view/029c886d1eb91a37f1115ce5.html
代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; int const maxn=1e5+5; int n,m,head[maxn],ct,mas; ll ans; struct N{ int to,next; N(int t=0,int n=0):to(t),next(n) {} }edge[maxn<<1]; struct T{ int ls,rs,siz,val,led,fa,dis; ll sum; }t[maxn]; int rd() { int ret=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return ret; } void add(int x,int y) { edge[++ct]=N(y,head[x]);head[x]=ct; edge[++ct]=N(x,head[y]);head[y]=ct; } int merge(int x,int y) { if(!x)return y; if(!y)return x; if(t[x].val<t[y].val)swap(x,y); t[x].rs=merge(t[x].rs,y); int ls=t[x].ls,rs=t[x].rs; t[x].sum=t[ls].sum+t[rs].sum+t[x].val; t[x].siz=t[ls].siz+t[rs].siz+1; if(t[ls].dis<t[rs].dis)swap(t[x].ls,t[x].rs);//不是swap(ls,rs) if(t[x].rs)t[x].dis=t[t[x].rs].dis+1;// else t[x].dis=0; return x; } int dfs(int x) { int rt=x; for(int i=head[x];i;i=edge[i].next) { int u=edge[i].to; if(u==t[x].fa)continue; rt=merge(rt,dfs(u)); } // while(t[x].sum>m) // { // t[x].sum-=t[x].val; // t[x].siz--; // x=merge(ls,rs); // } while(t[rt].sum>m)rt=merge(t[rt].ls,t[rt].rs); ans=max(ans,(ll)t[rt].siz*t[x].led);//不是 t[rt].led ，因为是选 x 作为管理者 return rt; } int main() { n=rd();m=rd(); for(int i=1;i<=n;i++) { t[i].fa=rd(); t[i].val=rd(); t[i].led=rd(); t[i].siz=1; t[i].sum=t[i].val; add(t[i].fa,i); if(t[i].fa==0)mas=i; } dfs(mas); printf("%lld",ans); return 0; }