1 /**************************************************************  2     Problem: 2809  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:804 ms  7     Memory:7624 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 typedef long long ll; 15 const int N = 100005; 16   17 struct heap{ 18     int v, l, r, dep; 19 }h[N]; 20 int cnt_heap; 21   22 struct edge { 23     int next, to; 24     edge() {} 25     edge(int _n, int _t) : next(_n), to(_t) {} 26 } e[N]; 27 int first[N], tot; 28   29 struct tree_node { 30     int cost, l, root; 31     ll sum, sz; 32 } tr[N]; 33   34 int n, m; 35 ll ans; 36   37 inline int read() { 38     int x = 0, sgn = 1; 39     char ch = getchar(); 40     while (ch < ‘0‘ || ‘9‘ < ch) { 41         if (ch == ‘-‘) sgn = -1; 42         ch = getchar(); 43     } 44     while (‘0‘ <= ch && ch <= ‘9‘) { 45         x = x * 10 + ch - ‘0‘; 46         ch = getchar(); 47     } 48     return sgn * x; 49 } 50   51 inline void add_edge(int x, int y) { 52     e[++tot] = edge(first[x], y); 53     first[x] = tot; 54 } 55   56 inline int new_heap(int x) { 57     h[++cnt_heap].v = x; 58     h[cnt_heap].l = h[cnt_heap].r = h[cnt_heap].dep = 0; 59     return cnt_heap; 60 } 61   62 int Merge(int x, int y) { 63     if (!x || !y) return x + y; 64     if (h[x].v < h[y].v) 65         swap(x, y); 66     h[x].r = Merge(h[x].r, y); 67     if (h[h[x].l].dep < h[h[x].r].dep) 68         swap(h[x].l, h[x].r); 69     h[x].dep = h[h[x].r].dep + 1; 70     return x; 71 } 72   73 inline int Top(int p) { 74     return h[p].v; 75 } 76   77 void Pop(int &p) { 78     p = Merge(h[p].l, h[p].r); 79 } 80   81 void dfs(int p) { 82     int x, y; 83     tr[p].root = new_heap(tr[p].cost); 84     tr[p].sum = tr[p].cost, tr[p].sz = 1; 85     for (x = first[p]; x; x = e[x].next) { 86         dfs(y = e[x].to); 87         tr[p].sum += tr[y].sum, tr[p].sz += tr[y].sz; 88         tr[p].root = Merge(tr[p].root, tr[y].root); 89     } 90     while (tr[p].sum > m) { 91         tr[p].sum -= Top(tr[p].root), Pop(tr[p].root); 92         --tr[p].sz; 93     } 94     ans = max(ans, tr[p].sz * tr[p].l); 95 } 96   97 int main() { 98     int i, x; 99     n = read(), m = read();100     for (i = 1; i <= n; ++i) {101         x = read();102         add_edge(x, i);103         tr[i].cost = read(), tr[i].l = read();104     }105     dfs(1);106     printf("%lld\n", ans);107     return 0;108 }