【bzoj2809】派遣 (左偏树)

传送门

题目分析

每个节点都是一颗（大根堆）左偏树，先按bfs序存入数组，然后倒着从底层开始：如果当前节点的子树sum > m 那么就把根节点删去，然后统计更新答案，并将这棵树和父节点合并。

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

const int N = 2e5 + ;

int n, m, fa[N], c[N], l[N];

int ecnt, adj[N], go[N], nxt[N];

typedef long long ll;

#define SZ(x) (x?x->sze:0)

#define S(x) (x?x->sum:0)

#define D(x) (x?x->dist:-1)

struct node{

    node *lc, *rc;

    int dist, sze, val;

    ll sum;

    node(){}

    node(int v):lc(NULL), rc(NULL), dist(), sze(), val(v), sum(v){}

    inline node* upt(){

        sze = SZ(lc) + SZ(rc) + ;

        sum = S(lc) + S(rc) + val;

        return this;

    }

}*tr[N];

int qn, que[N], root;

ll ans;

inline void addEdge(int u, int v){

    nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v;

}

inline node* Merge(node *u, node *v){

    if(!u) return v;

    if(!v) return u;

    if(u->val < v->val) swap(u, v);

    u->rc = Merge(u->rc, v);

    if(D(u->rc) > D(u->lc)) swap(u->lc, u->rc);

    u->dist = D(u->rc) + ;

    return u->upt();

}

inline void handle(int u){

    while(tr[u]->sum > m)

        tr[u] = Merge(tr[u]->lc, tr[u]->rc);

}

inline void solve(){

    que[qn = ] = root;

    for(int ql = ; ql <= qn; ql++){

        int u = que[ql];

        for(int e = adj[u]; e; e = nxt[e])

            que[++qn] = go[e];

    }

    for(int ql = qn; ql >= ; ql--){

        int u = que[ql], f = fa[u];

        handle(u);

        ans = max(ans, 1LL * tr[u]->sze * l[u]);

        tr[f] = Merge(tr[f], tr[u]);

    }

    handle(root);

    ans = max(ans, 1LL * tr[root]->sze * l[root]);

}

inline int read(){

    int i = , f = ; char ch = getchar();

    for(; (ch < '' || ch > '') && ch != '-'; ch = getchar());

    if(ch == '-') f = -, ch = getchar();

    for(; ch >= '' && ch <= ''; ch = getchar())

        i = (i << ) + (i << ) + (ch - '');

    return i * f;

}

inline void wr(ll x){

    if(x < ) putchar('-'), x = -x;

    if(x > ) wr(x / );

    putchar(x %  + '');

}

int main(){

    n = read(), m = read();

    for(int i = ; i <= n; i++){

        fa[i] = read(), c[i] = read(), l[i] = read();

        tr[i] = new node(c[i]);

        if(fa[i] == ) root = i;

        else addEdge(fa[i], i);

    }

    solve();

    wr(ans);

    return ;

}