(luogu1552)派遣(APIO2012)

发表于 | 分类于 ， ，

原题链接

思路:

树上对子树的问题可以考虑将子树向上合并来解决.

对于本题, 可以使用可并堆来向上合并.

具体来说, 由于被雇佣的忍者除薪水外本质上是一样的, 当超出预算时先排除薪水较高的更优.

于是可以构造一个大根堆, 同时维护当前堆中薪水总和, 当总和超出预算时将堆顶弹出直至总和小于等于预算.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Mn(100500);

template<typename T>
void qrd(T& x) {
    x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c-'0';
        c = getchar();
    }
}

int n,m;
/*题中的树结构*/
vector<int> tsn[Mn];    //子节点
int c[Mn], l[Mn];   //薪水, 领导力
/*左偏树结构*/
int hrt[Mn], sz[Mn], sn[Mn][2], fa[Mn]; //堆的根结点编号, 大小, 左右儿子, 所在堆的根
int d[Mn];  //距离
LL sum[Mn]; //堆中薪水总和
int getr(int x) {   //找根(路径压缩)
    return fa[x]==0 ? x : fa[x] = getr(fa[x]);
}
int merge(int x,int y) {    //堆合并
    if(!y) {
        return x;
    }
    if(!x) {
        return y;
    }
    if(c[x]<c[y]) {
        swap(x,y);
    }
    sn[x][1] = merge(sn[x][1],y);
    fa[sn[x][1]] = x;
    if(d[sn[x][0]]<d[sn[x][1]]) {
        swap(sn[x][0],sn[x][1]);
    }
    d[x] = d[sn[x][1]] + 1;
    return x;
}
int pop(int x) {
    fa[sn[x][0]] = fa[sn[x][1]] = 0;
    int nrt = merge(sn[x][0],sn[x][1]);
    fa[x] = nrt;
    return nrt;
}

LL ans(0);
void dfs(int x) {   //深搜, 回溯时向上合并
    for(int a: tsn[x]) {
        dfs(a);
        /*合并*/
        sz[x] += sz[a];
        sum[x] += sum[a];
        hrt[x] = merge(hrt[x],hrt[a]);
    }
    while(sum[x]>m) {   //超出预算时弹出
        --sz[x];
        sum[x] -= c[hrt[x]];
        hrt[x] = pop(hrt[x]);
    }
    ans = max(ans,1ll * sz[x] * l[x]);  //尝试以该子树更新答案
}

int main() {
    qrd(n), qrd(m);
    for(int i(1);i<=n;++i) {
        int b;
        qrd(b), qrd(c[i]), qrd(l[i]);
        tsn[b].push_back(i);
        hrt[i] = i, sum[i] = c[i], sz[i] = 1;
    }
    dfs(1);
    printf("%lld",ans);
    return 0;
}