[APIO 2012] 派遣

题目大意

nn 名忍者,每名忍者有一个上级(当然,最上级的那位没有),同时每名忍者有薪水 sis_i、领导力 lil_i,现选定一批忍者,这些忍者均是某一个忍者(作为管理者)的下级(管理者可以不选),将获得满意度:管理者领导力×\times所选忍者个数。求在薪水预算 mm 范围内的最大满意度。

1n100,0001 \leqslant n \leqslant 100,000

1m1,000,000,0001 \leqslant m \leqslant 1,000,000,000

1li1,000,000,0001 \leqslant l_i \leqslant 1,000,000,000

题目链接

【APIO 2012】派遣 - Luogu 1552

题解

dfs 序 ++ 主席树。

一个节点为根的子树在 dfs 序上是连续的。对于每一个节点,考虑其子树的区间,要使满意度更大,应该从薪水少的开始选,直到薪水和会超过预算,该操作可以用主席树做到 O(logn)O(\log n)

对于数据的处理要特别提一下:离散化时,相同的数应化为不同的数。(一开始没有意识到,各种 WA,于是在 COGS 上提了第一道题,找到了一份小的数据才发现问题的。。。不过要在「题目链接」中添加 COGS 的话,就要改所有的博文了。。。)

本题标算好像是左偏树,然而我不会。。。可是主席树常数好大。。。

VW:复杂度能和标算同阶就好啦

代码

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <cstdio>
#include <algorithm>
// #define DBG
const int MAXN = 100005;
struct Edge;
struct Node {
Edge *e;
Node *fa;
int dfn, rDfn, w;
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next;
Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {}
};
void addEdge(int u, int v) {
N[u].e = new Edge(&N[u], &N[v]);
N[v].e = new Edge(&N[v], &N[u]);
}
struct Ninja {
int s, l, id;
bool operator<(const Ninja &another) const {
return s < another.s;
}
} a[MAXN];
bool cmp(const Ninja &a, const Ninja &b) {
return a.id < b.id;
}
int map[MAXN], n;
void discretization() {
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) map[i] = a[i].s, a[i].s = i;
std::sort(a + 1, a + n + 1, cmp);
}
struct PSegT {
struct Node {
Node *lc, *rc;
int l, r, cnt;
long long sum;
Node(int l, int r, Node *lc = NULL, Node *rc = NULL) : l(l), r(r), lc(lc), rc(rc), cnt((lc ? lc->cnt : 0) + (rc ? rc->cnt : 0)), sum((lc ? lc->sum : 0) + (rc ? rc->sum : 0)) {}
Node(int l, int r, int cnt) : l(l), r(r), cnt(cnt), sum(cnt * (long long) map[l]), lc(NULL), rc(NULL) {}
void pushDown() {
if (lc && rc) return;
int mid = l + (r - l) / 2;
if (!lc) lc = new Node(l, mid);
if (!rc) rc = new Node(mid + 1, r);
}
Node *insert(int num) {
if (num < l || num > r) return this;
if (num == l && num == r) return new Node(l, r, this->cnt + 1);
int mid = l + (r - l) / 2;
pushDown();
if (num <= mid) return new Node(l, r, lc->insert(num), rc);
else return new Node(l, r, lc, rc->insert(num));
}
int rank() {
return lc ? lc->cnt : 0;
}
} *roots[MAXN];
int n;
void build(int a[], int n) {
this->n = n;
roots[0] = new Node(1, n);
for (int i = 1; i <= n; i++) roots[i] = roots[i - 1]->insert(a[i]);
}
int query(int l, int r, int m) {
Node *L = roots[l - 1], *R = roots[r];
int res = 0;
while (R->sum - L->sum > m) {
#ifdef DBG
printf("query in [%d, %d]\n", l, r);
printf(" L-([%d, %d], cnt = %d, sum = %lld)\n", L->l, L->r, L->cnt, L->sum);
printf(" R-([%d, %d], cnt = %d, sum = %lld)\n", R->l, R->r, R->cnt, R->sum);
#endif
L->pushDown();
R->pushDown();
long long temp = R->lc->sum - L->lc->sum;
#ifdef DBG
printf(" temp = %lld, res += %d\n", temp, R->lc->cnt - L->lc->cnt);
#endif
if (temp <= m) {
m -= temp;
res += R->lc->cnt - L->lc->cnt;
L = L->rc;
R = R->rc;
} else {
L = L->lc;
R = R->lc;
}
}
#ifdef DBG
printf("query in [%d, %d], return %d\n", l, r, res + R->cnt - L->cnt);
#endif
return res + R->cnt - L->cnt;
}
} pst;
int s[MAXN];
void dfs(Node *u, Node *fa = NULL) {
static int dfsClock = 0;
u->dfn = ++dfsClock;
s[dfsClock] = u->w;
for (Edge *e = u->e; e; e = e->next) {
if (e->v != fa) dfs(e->v, u);
}
u->rDfn = dfsClock;
}
int main() {
int m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
int f;
scanf("%d %d %d", &f, &a[i].s, &a[i].l);
if (f != 0) addEdge(i, f);
a[i].id = i;
}
discretization();
for (int i = 1; i <= n; i++) N[i].w = a[i].s;
dfs(&N[1]);
#ifdef DBG
for (int i = 1; i <= n; i++) printf("N[%d].dfn = %d\n", i, N[i].dfn);
#endif
pst.build(s, n);
long long ans = 0;
for (int i = 1; i <= n; i++) ans = std::max(ans,
(long long) pst.query(N[i].dfn, N[i].rDfn, m) * a[i].l);
printf("%lld\n", ans);
return 0;
}