BZOJ 2809 「APIO2012」派遣

如果是正常的我肯定是果断写一个线段树合并 + 线段树上二分，然而今天学了左偏树那就写一写。
（如果对于每个点有单独的 M 左偏树就没法做了）

显然要从小到大选数，直到最后一个能满足总和不超过 M 的，这样一定是最大的。
所以权值线段树上二分吧！
（大雾）

不过左偏树也能做，就是维护子树内的大根堆，然后一直弹直到总和不超过 M 即可。
问题在于如何维护。
由于 M 不变，所以之前被弹掉的之后不可能再有贡献，于是每个点做完之后合并到父亲处即可。

代码：

#include <cstdio>
#include <algorithm>
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);
}