这一题中各位忍者的关系其实是一棵树：
b[i]是他的上司，也是他的父节点
一个父节点可能有多个儿子
父子关系就是命令的传达关系，父亲能传给儿子
所以如果选中一个管理者，那他就是这棵树的根
因为忍者只要祖宗是管理者，就可以传话，
所以管理者可以选择的忍者的范围就是他的所有子孙
而传话的忍者也可以不被调遣，管理者也可以
所以选择忍者时，不用要求这个被选择点的父亲也被选择
那么把所有点放到一个堆中，然后按照w的值重新开始排序，合并
找最大值删除就好
//思路：其实这道题很保留，枚举管理者，枚举被派遣的人 //但是，是有方法的枚举 #include<cstdio> #include<cstdlib> #include<vector> #include<queue> using namespace std; int n,m; long long ans; const int N=100003; vector <int > son[N]; int b[N],w[N],val[N]; int fa[N]; int find(int x) { return fa[x]==0?x:fa[x]=find(fa[x]); } int merge(int a,int b)//这里是w的最大堆 { if(a==b) return a; if(w[a]<=w[b]) return fa[a]=b,son[b].push_back(a), b; else return fa[b]=a,son[a].push_back(b), a; } int del(int x) { queue <int> s; int siz=son[x].size() ; for(int i=0;i<siz;i++) { int t=son[x][i]; fa[t]=0; s.push(t); } while((siz--)>1) { int a=s.front();s.pop(); int b=s.front();s.pop(); s.push(merge(a,b)); } if(!s.empty() ) fa[x]=s.front(); son[x].clear() ; return w[x]; } int sz[N]; long long sum[N]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d%d",&b[i],&w[i],&val[i]); ans=max((long long)val[i],ans);//1 sz[i]=1,sum[i]=w[i]; } for(int i=n;i;i--)//每一个忍者的老板的编号一定小于自己的编号Bi<i //这连欧拉序都省了， 直接从n（就是底部）开始遍历，往上走 { int f=b[i];//这就是根 sz[f]+=sz[i],sum[f]+=sum[i]; merge(find(i),find(f));//!!!!!!!这里不可以直接写f， //因为f有不止一个儿子，在之前已经被拉出来merge过了，find（f）不一定等于f while(sum[f]>m) { sum[f]-=del(find(f)); sz[f]--; } ans=max(ans,sz[f]*1LL*val[f] ); } printf("%lld",ans); return 0; }