给一棵N个点的树，然后问以某个点作为节点的时候，其子树中在购买力为M的情况下最多购买多少个节点，对于所有的子树，求节点数乘以该子树根节点的b值的最大值。
于是，想到的做法就是对于每个点去维护一个大根堆，如果大根堆内的和超过了M，那么就需要弹出最大的节点，于是，就是维护一个大根堆的合并了，合并的话，用左偏树最快了，于是我们在左偏树上pushup就可以了。
1 #include <iostream>
2 #include <cstdio>
3 #include <cmath>
4 #include <string>
5 #include <cstring>
6 #include <algorithm>
7 #include <limits>
8 #include <vector>
9 #include <stack>
10 #include <queue>
11 #include <set>
12 #include <map>
13 #include <bitset>
14 #include <unordered_map>
15 #include <unordered_set>
16 #define lowbit(x) ( x&(-x) )
17 #define pi 3.141592653589793
18 #define e 2.718281828459045
19 #define INF 0x3f3f3f3f
20 #define HalF (l + r)>>1
21 #define lsn rt<<1
22 #define rsn rt<<1|1
23 #define Lson lsn, l, mid
24 #define Rson rsn, mid+1, r
25 #define QL Lson, ql, qr
26 #define QR Rson, ql, qr
27 #define myself rt, l, r
28 #define pii pair<int, int>
29 #define MP(a, b) make_pair(a, b)
30 using namespace std;
31 typedef unsigned long long ull;
32 typedef unsigned int uit;
33 typedef long long ll;
34 const int maxN = 1e5 + 7;
35 int N, root[maxN];
36 ll M, b[maxN];
37 struct node
38 {
39 ll val, sum; int d, c[2], fa, siz;
40 node(ll a=0, ll su=0, int b=0, int c1=0, int c2=0, int f=0, int s=0):val(a), sum(su), d(b), c{c1, c2}, fa(f), siz(s) {}
41 } t[maxN];
42 int fid(int x) { return x == t[x].fa ? x : t[x].fa = fid(t[x].fa); }
43 void pushup(int x)
44 {
45 t[x].sum = t[t[x].c[0]].sum + t[t[x].c[1]].sum + t[x].val;
46 t[x].siz = t[t[x].c[0]].siz + t[t[x].c[1]].siz + 1;
47 }
48 int Merge(int x, int y)
49 {
50 if(!x || !y) return x | y;
51 if(t[x].val < t[y].val) swap(x, y);
52 t[x].c[1] = Merge(t[x].c[1], y);
53 t[t[x].c[1]].fa = x;
54 if(t[t[x].c[0]].d < t[t[x].c[1]].d) swap(t[x].c[0], t[x].c[1]);
55 t[x].d = t[t[x].c[1]].d + 1;
56 pushup(x);
57 return x;
58 }
59 int Pop(int x)
60 {
61 int f = fid(x);
62 while(t[f].sum > M)
63 {
64 t[t[f].c[0]].fa = t[f].c[0];
65 t[t[f].c[1]].fa = t[f].c[1];
66 t[f].fa = Merge(t[f].c[0], t[f].c[1]);
67 f = t[f].fa;
68 }
69 return f;
70 }
71 vector<int> to[maxN];
72 ll ans = 0;
73 void dfs(int u)
74 {
75 int fu, fv; root[u] = u;
76 for(int v : to[u])
77 {
78 dfs(v);
79 fu = fid(root[u]); fv = fid(root[v]);
80 root[u] = Merge(fu, fv);
81 }
82 root[u] = Pop(fid(u));
83 ans = max(ans, t[root[u]].siz * b[u]);
84 }
85 int main()
86 {
87 scanf("%d%lld", &N, &M);
88 for(int i=1, ff; i<=N; i++)
89 {
90 scanf("%d%lld%lld", &ff, &t[i].val, &b[i]);
91 t[i].fa = i; t[i].siz = 1; t[i].sum = t[i].val;
92 if(ff) to[ff].push_back(i);
93 }
94 dfs(1);
95 printf("%lld\n", ans);
96 return 0;
97 }