【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 + 5;
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(0), sze(1), val(v), sum(v){}
    inline node* upt(){
        sze = SZ(lc) + SZ(rc) + 1;
        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) + 1;
    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 = 1] = root;
    for(int ql = 1; 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 >= 2; 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 = 0, f = 1; char ch = getchar();
    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
    if(ch == '-') f = -1, ch = getchar();
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        i = (i << 3) + (i << 1) + (ch - '0');
    return i * f;
}

inline void wr(ll x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) wr(x / 10);
    putchar(x % 10 + '0');
}

int main(){
    n = read(), m = read();
    for(int i = 1; i <= n; i++){
        fa[i] = read(), c[i] = read(), l[i] = read();
        tr[i] = new node(c[i]);
        if(fa[i] == 0) root = i;
        else addEdge(fa[i], i);
    }
    solve();
    wr(ans);
    return 0;
}