[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;
}

一言

我们是如此的担心着未来会发生的事情，因此忘记了慢下来享受现在。