C++ 解法, 执行用时: 151ms, 内存消耗: 19588K, 提交时间: 2021-08-04 14:45:26

//322971G 
/*
  @Author: YooQ
*/
#include <bits/stdc++.h>
using namespace std;
#define sc scanf
#define pr printf
#define ll long long
#define int long long
#define FILE_OUT freopen("out", "w", stdout);
#define FILE_IN freopen("in", "r", stdin);
#define debug(x) cout << #x << ": " << x << "\n";
#define AC 0
#define WA 1
#define INF 0x3f3f3f3f
const ll MAX_N = 1e6+5;
const ll MOD = 1e9+7;
int N, M, K;

int arr[MAX_N];
int brr[MAX_N];
int ans = 0;

int head[MAX_N];
int tot = 0;

struct Edge{
	int to, nxt;
}edge[MAX_N];

void addEdge(int u, int v) {
	edge[tot].nxt = head[u];
	edge[tot].to = v;
	head[u] = tot++;
	edge[tot].nxt = head[v];
	edge[tot].to = u;
	head[v] = tot++;
}

struct Lefitst {
	struct Tr{
		int k, l, r, dis;
	}tr[MAX_N];
	
	int sz;
	int indx;
	int root;
	int price;
	
	int mk(int k) {
		tr[++indx] = {k, 0, 0, 0};
		return indx;
	}
	
	int merge(int x, int y) {
		if (!x || !y) return x | y;
		if (tr[x].k < tr[y].k) swap(x, y);
		tr[x].r = merge(tr[x].r, y);
		if (tr[tr[x].r].dis > tr[tr[x].l].dis) swap(tr[x].l, tr[x].r);
		tr[x].dis = tr[tr[x].r].dis + 1;
		return x;
	}
	
	void insert(int k) {
		root = merge(root, mk(k));
		++sz;
		price += k;
	}
	
	int top() {
		return tr[root].k;
	}
	
	void pop() {
		--sz;
		price -= top();
		root = merge(tr[root].l, tr[root].r);
	}
		
}tr;


int sz[MAX_N];
int son[MAX_N];
int father[MAX_N];

void dfs(int u, int from) {
	sz[u] = 1;
	son[u] = 0;
	father[u] = from;
	int v;
	for (int i = head[u];~i;i=edge[i].nxt) {
		if ((v=edge[i].to) == from) continue;
		dfs(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) {
			son[u] = v;
		}
	}
}

void update(int u) {
	tr.insert(arr[u]);
}

void calc(int u) {
	update(u);
	int v;
	for (int i = head[u];~i;i=edge[i].nxt) {
		if ((v=edge[i].to) == father[u]) continue;
		calc(v);
	}
}

void del(int u) {
	tr.indx = 0;
	tr.sz = 0;
	tr.root = 0;
	tr.price = 0;
}

void get_ans(int u) {
	while (tr.price > M) {
		tr.pop();
	}
	ans = max(ans, tr.sz * brr[u]);
}

void dsu(int u, int opt) {
	int v;
	for (int i = head[u];~i;i=edge[i].nxt) {
		if ((v=edge[i].to) == son[u] || v == father[u]) continue;
		dsu(v, 1);
	}
	if (son[u]) dsu(son[u], 0);
	update(u);
	for (int i = head[u];~i;i=edge[i].nxt) {
		if ((v=edge[i].to) == son[u] || v == father[u]) continue;
		calc(v);
	}
	get_ans(u);
	if (opt) del(u);
}

void init() {
	memset(head, -1, sizeof head);
	tot = 0;
}

void solve(){
	init();
	sc("%lld%lld", &N, &M);
	int u, v;
	for (int i = 1; i <= N; ++i) {
		sc("%lld", &u);
		sc("%lld%lld", &arr[i], &brr[i]);
		if (u) addEdge(u, i);
	}
	dfs(1, 0);
	dsu(1, 0);
	cout << ans;
}

signed main()
{
	#ifndef ONLINE_JUDGE
	//FILE_IN
	FILE_OUT
	#endif
	int T = 1;//cin >> T;
	while (T--) solve();

	return AC;
}