题目大意：给出一棵树，每个节点有两个值，各自是这个忍者的薪水和忍者的领导力。客户的惬意程度是这个点的领导力乘可以取得人数。前提是取的人的薪水总和不超过总的钱数。
思路：仅仅能在子树中操作。贪心的想，我们仅仅要这个子树中cost最小的那些点就能够了。
所以就深搜一次。每到一个节点上。把自己和全部子节点的平衡树启示式和并，然后保留不超过总钱数的人数。统计。数据范围比較大，能开long long的地方不要吝啬。
PS：吐槽一下，一開始这个题一直TTT。我以为是我常数写的太大了。别人都用左偏堆写。是不是平衡树已经成为了时代的眼泪了。
。。
后来我搞到了測点。跑了一下第一组数据等了1分多钟都没出解。
我感觉我又要重写了。就出去转转。十分钟之后我回来发现竟然出解了。并且竟然还对了！！
然后我细致看了一遍程序。
。
。发现是启示式合并写反了。。。。写反了。。。反了。。。
了。。。
CODE：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100010
using 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;
}