题意
??有一棵n个节点的树，每个节点有两个权值：
Ci 和Wi，对于一个节点u，我们可以从u 的子树中选出一个点集S，满足∑Cv≤M，v∈S ，求所有满足条件的S中，Wu?|S| 的最大值
解法
左偏树/平衡树+贪心：
??考虑到所求值是Wu?|S|，所以与其他节点的W值无关
又因为要满足∑Cv≤M，v∈S ，所以为了使|S|尽可能大，所以我们总是会选取u的子树内C 值较小的节点来凑齐M
选出子树内C 值较小的点，我们可以选择使用平衡树（Splay）或者是左偏树
??相比较而言，左偏树的代码比较容易实现，效率也挺高的，如果追求更高的效率，可以考虑平衡树。
??若使用左偏树的大根堆，那么令sumu表示u的子树内部的∑Cv ，sizu表示|S|，如果sumu＞M，则删去堆顶元素的贡献，然后sizu?1，并合并左偏树根的左右儿子
??若使用小根堆，那么变成累加即可（其实还是大根堆好写一些）
复杂度
O（nlogn）
代码
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define Rint register int
#define Lint long long int
using namespace std;
const Lint INF=0x3f3f3f3f;
const int MAXN=100010;
struct node
{int next,to;
}t[MAXN*2];
int head[MAXN],num;
Lint sum[MAXN],siz[MAXN];
int dis[MAXN],rt[MAXN];
int ls[MAXN],rs[MAXN];
Lint c[MAXN],w[MAXN];
int n,m,Rt;
Lint ans;
void add(int u,int v)
{t[++num]=(node){ head[u],v };head[u]=num;
}
int merge(Rint x,Rint y)
{if( !x || !y ) return x+y;if( c[x]<c[y] ) swap( x,y );rs[x]=merge( rs[x],y );if( dis[rs[x]]>dis[ls[x]]) swap( ls[x],rs[x] );if( !rs[x] ) dis[x]=0;else dis[x]=dis[rs[x]]+1;return x;
}
void dfs(Rint k,Rint fa)
{rt[k]=k;siz[k]++,sum[k]+=c[k];for(int i=head[k],x; i ;i=t[i].next){x=t[i].to;if( x==fa ) continue ;dfs( x,k );siz[k]+=siz[x],sum[k]+=sum[x];rt[k]=merge( rt[k],rt[x] );}while( sum[k]>m && siz[k] ){sum[k]-=c[rt[k]],siz[k]--;rt[k]=merge( ls[rt[k]],rs[rt[k]] );}if( sum[k]<=m ) ans=max( ans,siz[k]*w[k] );
}
int main()
{scanf("%d%d",&n,&m);for(int i=1,x;i<=n;i++){scanf("%d%lld%lld",&x,&c[i],&w[i]);if( x ) add( i,x ),add( x,i );else Rt=i;}dfs( Rt,0 );printf("%lld\n",ans);return 0;
}