洛谷

题意：

一棵树，每个点有权值a与权值b。每个点的答案为该点的权值a乘子树（包括它自己）中选择的节点个数，其中要求选中的节点的权值和小于等于给定的M（仅一组询问）。问所有点的答案中最大的是多少。

解1：

如果单独对某个点做暴力询问，显然可以贪心选择权值b最小的节点。而这样的问题很方便在权值线段树上二分出答案。因此我们就得到了两种做法

主席树

是在主席树的题单里面看到这道题的，首先从主席树的角度考虑。由于这道题是子树中操作，显然应该利用dfs序先把树摊成序列。然后直接按照主席树的最经典应用做即可。

线段树合并

这种题主席树做法和线段树合并的做法通常是成对出现？对于每棵树的所有儿子做线段树启发式合并即可。

解2：

主席树的做法很显然，在想线段树合并做法时候发现直接可并堆做就好了，少写很多东西（thanks to pbds）（就算没有pbds，左偏树总也比主席树细节少）。每个点建一个大根堆，把儿子的堆都合并来，把自己插进去，维护每个堆的b权值和，如果和大于M就一直pop到和小于等于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
const int maxn=111111;
__gnu_pbds::priority_queue<int,less<int>,__gnu_pbds::pairing_heap_tag>h[maxn];
LL sum[maxn];
int n,m;//sum: sum of salary
int c[maxn],l[maxn];
LL ans=0;
struct TREE
{
    int nxt[maxn<<1],to[maxn<<1],first[maxn],cnt,fa[maxn];
    void addedge(int u,int v)
	{
        nxt[++cnt]=first[u];
        first[u]=cnt;
        to[cnt]=v;
    }
    void addedge2(int u,int v){addedge(u,v);addedge(v,u);}
    void dfs(int x)
	{
        for (int q=first[x];q;q=nxt[q]) if (to[q]!=fa[x])
        {
            dfs(to[q]);
            h[x].join(h[to[q]]);
            sum[x]+=sum[to[q]];
        }
        h[x].push(c[x]);
        sum[x]+=c[x];
        while (sum[x]>m)
        {
            sum[x]-=h[x].top();
            h[x].pop();
        }
        ans=max(ans,(LL)((LL)l[x]*h[x].size()));
    }
}tree;
int main()
{
    read(n,m);
    rep(i,1,n)
    {
        read(tree.fa[i],c[i],l[i]);
        if (i!=0) tree.addedge2(i,tree.fa[i]);
    }
    tree.dfs(1);
    printf("%lld\n",ans);
    return 0;
}