[luogu1552][派遣]

題目鏈接

思路

首先肯定要樹形dp，一直沒想到怎麼用左偏樹。如果不斷彈出又不斷地合併複雜度不就太高了。瞄了眼題解才知道可以直接用大根樹。然後記錄出當前這棵左偏樹的大小(樹裡面所有點的薪水之和)以及點的個數。然後不斷的刪點。直到薪水滿足條件為止。

代碼

#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
vector<int> son[N];
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll m,a[N],w[N],siz[N];
int ch[N][2],fa[N],n,dist[N];
ll ans,num[N];
int merge(int x,int y) {
    if(x == 0 || y == 0) return x == 0 ? y : x;
    if(a[x] > a[y] || (x > y && a[x] == a[y])) swap(x,y);
    ch[y][1] = merge(x,ch[y][1]);
    fa[x] = y;
    if(dist[ch[y][1]] > dist[ch[y][0]]) swap(ch[y][1],ch[y][0]);
    dist[y] = dist[ch[y][1]] + 1;
    return y;
}
ll pop(int x) {
    int k = merge(ch[x][0],ch[x][1]);
    ch[x][1] = ch[x][0] = 0;
    siz[k] = siz[x] - a[x];
    num[k] = num[x] - 1;
    return k;
}
int dfs(int u) {
    int nn = son[u].size();
    int now = u;
    siz[now] = a[now];
    num[now] = 1;
    for(int i = 0;i < nn;++i) {
        int v = son[u][i];
        int k = dfs(v);
        int ls = merge(k,now);
        siz[ls] = siz[k] + siz[now];
        num[ls] = num[k] + num[now];
        now = ls;
    }
    while(siz[now] > m) now = pop(now);
    ans = max(ans,w[u] * num[now]);
    return now;
}
int main() {
    n = read(), m = read();
    dist[0] = -1;
    int rt = 0;
    for(int i = 1;i <= n;++i) {
        int fat = read();
        a[i] = read(),w[i] = read();
        son[fat].push_back(i);
        if(fat == 0) rt = i;
    }
    dfs(rt);
    cout<<ans;
    return 0;
}

一言

我們是如此的擔心著未來會發生的事情，因此忘記了慢下來享受現在。