题目大意：给出一棵树，每个节点有两个值，各自是这个忍者的薪水和忍者的领导力。客户的惬意程度是这个点的领导力乘可以取得人数。前提是取的人的薪水总和不超过总的钱数。

思路：仅仅能在子树中操作。贪心的想，我们仅仅要这个子树中cost最小的那些点就能够了。

所以就深搜一次。每到一个节点上。把自己和全部子节点的平衡树启示式和并，然后保留不超过总钱数的人数。统计。数据范围比較大，能开long long的地方不要吝啬。

PS：吐槽一下，一開始这个题一直TTT。我以为是我常数写的太大了。别人都用左偏堆写。是不是平衡树已经成为了时代的眼泪了。

。。

后来我搞到了測点。跑了一下第一组数据等了1分多钟都没出解。

我感觉我又要重写了。就出去转转。十分钟之后我回来发现竟然出解了。并且竟然还对了！！

然后我细致看了一遍程序。

。

。发现是启示式合并写反了。。。。写反了。。。反了。。。

了。。。

CODE：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define MAX 100010using namespace std;struct Complex{	long long cost,leader;}point[MAX];struct Treap{	int random,size,cnt;	long long val,sum;	Treap *son[2];	Treap(long long _) {		val = sum = _;		size = cnt = 1;		random = rand();		son[0] = son[1] = NULL;	}	int Compare(long long x) {		if(x == val)	return -1;		return x > val;	}	void Maintain() {		size = cnt;		sum = val * cnt;		if(son[0] != NULL)	size += son[0]->size,sum += son[0]->sum;		if(son[1] != NULL)	size += son[1]->size,sum += son[1]->sum;	}}*tree[MAX];long long points,money;int head[MAX],total;int next[MAX << 1],aim[MAX << 1];long long ans;inline void Add(int x,int y){	next[++total] = head[x];	aim[total] = y;	head[x] = total;}inline void Rotate(Treap *&a,bool dir){	Treap *k = a->son[!dir];	a->son[!dir] = k->son[dir];	k->son[dir] = a;	a->Maintain(),k->Maintain();	a = k;}inline void Insert(Treap *&a,long long x){	if(a == NULL) {		a = new Treap(x);		return ;	}	int dir = a->Compare(x);	if(dir == -1)	++a->cnt;	else {		Insert(a->son[dir],x);		if(a->son[dir]->random > a->random)			Rotate(a,!dir);	}	a->Maintain();}inline int FindMax(Treap *a){	return a->son[1] == NULL ?
        
       
      
     

a->val:FindMax(a->son[1]); } inline void Delete(Treap *&a,long long x) { int dir = a->Compare(x); if(dir != -1) Delete(a->son[dir],x); else { if(a->cnt > 1) --a->cnt; else { if(a->son[0] == NULL) a = a->son[1]; else if(a->son[1] == NULL) a = a->son[0]; else { bool _ = (a->son[0]->random > a->son[1]->random); Rotate(a,_); Delete(a->son[_],x); } } } if(a != NULL) a->Maintain(); } void Transfrom(Treap *&from,Treap *&aim) { if(from == NULL) return ; Transfrom(from->son[0],aim); Transfrom(from->son[1],aim); for(int i = 1; i <= from->cnt; ++i) Insert(aim,from->val); delete from; from = NULL; } void DFS(int x) { tree[x] = new Treap(point[x].cost); if(point[x].cost <= money) ans = max(ans,(long long)point[x].leader); if(!head[x]) return ; for(int i = head[x]; i; i = next[i]) { DFS(aim[i]); if(tree[x]->size < tree[aim[i]]->size) swap(tree[x],tree[aim[i]]); Transfrom(tree[aim[i]],tree[x]); } while(tree[x]->sum > money) Delete(tree[x],FindMax(tree[x])); ans = max(ans,(long long)tree[x]->size * point[x].leader); } int main() { cin >> points >> money; for(int x,i = 1; i <= points; ++i) { scanf("%d%lld%lld",&x,&point[i].cost,&point[i].leader); Add(x,i); } DFS(0); cout << ans << endl; return 0; }