这题的最优解法是可并堆，从上往下合并及删点，标准的O(nlogn)解法。
为了练习主席树，特用主席树写一发，可以按dfs序建立主席树，对每个子树进行查询。
总时间5232毫秒，要垫底了...
看来需要去借鉴一下别人的主席树模板了。
/**************************************************************
Problem: 2809
User: chad
Language: C++
Result: Accepted
Time:5232 ms
Memory:98144 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<iomanip>
#include<map>
#include<queue>
using namespace std;
#define mem1(i,j) memset(i,j,sizeof(i))
#define mem2(i,j) memcpy(i,j,sizeof(i))
#define LL long long
#define up(i,j,n) for(LL i=(j);i<=(n);i++)
#define FILE "dealing"
#define poi vec
#define eps 1e-10
#define mid (l+r>>1)
#define db double
const LL maxn=102000,inf=1000000000,mod=1000000007;
LL read(){
LL x=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0',ch=getchar();}
return f*x;
}
bool cmax(LL& a,LL b){return a<b?a=b,true:false;}
bool cmin(LL& a,LL b){return a>b?a=b,true:false;}
LL n,m;
struct node{LL y,next;}e[maxn<<1];
int len=0,linkk[maxn<<1],L[maxn],id[maxn],fa[maxn],v[maxn],q[maxn],pre[maxn],t[maxn],low[maxn],dfs_clock=0;
void insert(LL x,LL y){e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;}
LL rt=0;
struct Node{LL x,y,z;}a[maxn];
bool cmp(const Node a,const Node b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
bool cmp2(const Node a,const Node b){return pre[a.y]<pre[b.y];}
bool cmp3(const Node a,const Node b){return a.y<b.y;}
void dfs(LL x){
pre[x]=++dfs_clock;
for(LL i=linkk[x];i;i=e[i].next){
if(e[i].y==fa[x])continue;
dfs(e[i].y);
}
low[x]=dfs_clock;
}
LL r[2200000],sum[2200000],c[2200000][2],val[2200000],cnt=0;
void updata(LL x){ //val的和
sum[x]=sum[c[x][0]]+sum[c[x][1]];
val[x]=val[c[x][0]]+val[c[x][1]];
}
void set(LL& o,LL rt,LL key,LL l,LL r){
if(!o)o=++cnt;
if(l==r){val[o]=a[key].x;sum[o]=1;return;}
if(key<=mid)c[o][1]=c[rt][1],set(c[o][0],c[rt][0],key,l,mid);
else c[o][0]=c[rt][0],set(c[o][1],c[rt][1],key,mid+1,r);
updata(o);
}
void init(){up(i,1,n)set(r[i],r[i-1],t[i],1,n);}
LL shu=0,y=m,d;
void walk(LL o1,LL o2,LL l,LL r){
if(val[c[o2][0]]-val[c[o1][0]]<=y)y-=(val[c[o2][0]]-val[c[o1][0]]),shu+=sum[c[o2][0]]-sum[c[o1][0]],d=1;
else d=0;
if(l==r)return;
if(!d)walk(c[o1][0],c[o2][0],l,mid);
else walk(c[o1][1],c[o2][1],mid+1,r);
}
LL query(LL L,LL R){
shu=0;y=m;walk(r[L],r[R],1,n);
return shu;
}
int main(){
//freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
n=read(),m=read();
up(i,1,n){ //薪水 领导力
fa[i]=read(),v[i]=read(),L[i]=read();
a[i].x=v[i],a[i].y=i;
if(!fa[i])rt=i;
else insert(i,fa[i]),insert(fa[i],i);
}
dfs(rt);
sort(a+1,a+n+1,cmp);
up(i,1,n)t[pre[a[i].y]]=i;
up(i,1,n)id[pre[i]]=i;//第i个位置的原节点为id[i]
init();
LL ans=0;
up(i,1,n)ans=max(ans,(LL)query(pre[i]-1,low[i])*L[i]);
cout<<ans<<endl;
return 0;
}