如果是正常的我肯定是果断写一个线段树合并 + 线段树上二分，然而今天学了左偏树那就写一写。
（如果对于每个点有单独的 \(M\) 左偏树就没法做了）
显然要从小到大选数，直到最后一个能满足总和不超过 \(M\) 的，这样一定是最大的。
所以权值线段树上二分吧！
（大雾）
不过左偏树也能做，就是维护子树内的大根堆，然后一直弹直到总和不超过 \(M\) 即可。
问题在于如何维护。
由于 \(M\) 不变，所以之前被弹掉的之后不可能再有贡献，于是每个点做完之后合并到父亲处即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using namespace std;
const int N = 1e5;
int n,m,r,fa[N + 5],c[N + 5],l[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
long long ans;
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
struct node
{
int val,dis,fa;
int sz;
long long sum;
int ls,rs;
} tree[N + 5];
int rt[N + 5],st[N + 5],top;
inline int new_node(int v)
{
static int tot = 0;
int p = top ? st[top--] : ++tot;
tree[p].val = v,tree[p].dis = tree[p].fa = tree[p].ls = tree[p].rs = 0;
tree[p].sum = v,tree[p].sz = 1;
return tot;
}
int merge(int p,int q)
{
if(!p || !q)
return p | q;
if(tree[p].val < tree[q].val)
swap(p,q);
tree[tree[p].rs = merge(tree[p].rs,q)].fa = p;
if(tree[tree[p].ls].dis < tree[tree[p].rs].dis)
swap(tree[p].ls,tree[p].rs);
tree[p].dis = tree[tree[p].rs].dis + 1;
tree[p].sum = tree[tree[p].ls].sum + tree[p].val + tree[tree[p].rs].sum;
tree[p].sz = tree[tree[p].ls].sz + 1 + tree[tree[p].rs].sz;
return p;
}
inline void pop(int &p)
{
st[++top] = p,tree[p = merge(tree[p].ls,tree[p].rs)].fa = 0;
}
void dfs(int p)
{
for(register int i = first[p];i;i = pre[i])
dfs(to[i]),rt[p] = merge(rt[p],rt[to[i]]);
for(;tree[rt[p]].sz && tree[rt[p]].sum > m;pop(rt[p]));
ans = max(ans,(long long)l[p] * tree[rt[p]].sz);
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d%d%d",fa + i,c + i,l + i),fa[i] ? (add(fa[i],i),1) : (r = i),rt[i] = new_node(c[i]);
dfs(r);
printf("%lld\n",ans);
}