#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x.size()))
#define all(x) x.begin(), x.end()
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
using ll = long long;
const char nl = '\n';
const int MX = 1e5 + 10;
struct Node {
int ls, rs;
ll mx, mn, lz;
Node(ll hi = 0, ll lo = 0) : ls(0), rs(0), mx(hi), mn(lo), lz(0) {}
};
Node st[int(15e6)];
int _nxt;
void addChild(int v) {
if(st[v].ls) return;
// cerr << v->mx << " " << v->mn << nl;
Node tmp(st[v].mx - st[v].lz, st[v].mn - st[v].lz);
st[v].ls = ++_nxt;
st[_nxt] = tmp;
st[v].rs = ++_nxt;
st[_nxt] = tmp;
}
void prop(int v) {
if(!st[v].ls) return;
ll& L = st[v].lz;
int _ls = st[v].ls;
int _rs = st[v].rs;
st[_ls].lz += L;
st[_ls].mx += L;
st[_ls].mn += L;
st[_rs].lz += L;
st[_rs].mx += L;
st[_rs].mn += L;
L = 0;
}
void pull(int v) {
st[v].mx = max(st[st[v].ls].mx, st[st[v].rs].mx);
st[v].mn = min(st[st[v].ls].mn, st[st[v].rs].mn);
}
void upd(int v, int b, int e, int l, int r, ll x) {
if(l >= r) return;
addChild(v);
if(b == l && e == r) {
st[v].mx += x;
st[v].mn += x;
st[v].lz += x;
return;
}
prop(v);
int m = (b + e) / 2;
upd(st[v].ls, b, m, l, min(r, m), x);
upd(st[v].rs, m, e, max(l, m), r, x);
pull(v);
}
void upd2(int v, int b, int e, int l, int r, ll x) {
if(l >= r || st[v].mn >= x) return;
addChild(v);
if(b == l && e == r && st[v].mx <= x) {
st[v].ls = st[v].rs = 0;
st[v].mx = x;
st[v].mn = x;
st[v].lz = 0;
return;
}
prop(v);
int m = (b + e) / 2;
upd2(st[v].ls, b, m, l, min(r, m), x);
upd2(st[v].rs, m, e, max(l, m), r, x);
pull(v);
}
ll qry(int v, int b, int e, int l, int r) {
if(l >= r) return 0;
addChild(v);
if(b == l && e == r) {
return st[v].mx;
}
prop(v);
int m = (b + e) / 2;
return max(qry(st[v].ls, b, m, l, min(r, m)), qry(st[v].rs, m, e, max(l, m), r));
}
vector<pair<int,ll>> leaves;
void getLeaves(int v, int b, int e) {
if(!v) return;
if(e - b == 1 || !st[v].ls) {
if(!sz(leaves) || st[v].mx > leaves.back().second) {
leaves.push_back({b, st[v].mx});
}
return;
}
prop(v);
int m = (b + e) / 2;
getLeaves(st[v].ls, b, m);
getLeaves(st[v].rs, m, e);
}
vector<int> adj[MX];
int tree[MX];
int val[MX], day[MX];
int n, m, k, sz[MX];
void dfsSz(int v) {
sz[v] = 1;
for(int u : adj[v]) {
dfsSz(u);
sz[v] += sz[u];
}
}
void dfs(int v) {
int big = -1;
for(int u : adj[v]) {
dfs(u);
if(big == -1 || sz[big] < sz[u]) {
big = u;
}
}
if(big == -1) {
tree[v] = ++_nxt;
} else {
tree[v] = tree[big];
}
//cerr << "doing: " << v+1 << nl;
for(int u : adj[v]) {
if(u != big) {
leaves.clear();
getLeaves(tree[u], 0, k);
ll prv = 0;
for(int i = 0; i < sz(leaves); i++) {
int nxt = i + 1 == sz(leaves) ? k : leaves[i + 1].first;
auto [pos, x] = leaves[i];
// cerr << prv << " " << x << " -> " << pos << " " << nxt << nl;
assert(prv <= x);
upd(tree[v], 0, k, pos, nxt, x);
prv = x;
}
}
}
if(day[v] != -1) {
ll me = val[v] + qry(tree[v], 0, k, 0, day[v]+1);
upd2(tree[v], 0, k, day[v], k, me);
// cerr << v+1 << ": " << me << nl;
}
}
void solve() {
cin >> n >> m >> k;
fill_n(day, n, -1);
for(int i = 1; i < n; i++) {
int p;
cin >> p; --p;
adj[p].push_back(i);
}
ll should = 0;
for(int i = 0; i < m; i++) {
int v;
cin >> v; --v;
cin >> day[v] >> val[v];
--day[v];
should += val[v];
}
dfsSz(0);
dfs(0);
cout << st[tree[0]].mx << nl;
// assert(tree[0]->mx <= should);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te = 1;
// cin >> te;
while(te--) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
472256 KB |
Output is correct |
2 |
Correct |
180 ms |
472272 KB |
Output is correct |
3 |
Correct |
181 ms |
472260 KB |
Output is correct |
4 |
Correct |
181 ms |
472280 KB |
Output is correct |
5 |
Correct |
203 ms |
472252 KB |
Output is correct |
6 |
Correct |
176 ms |
472324 KB |
Output is correct |
7 |
Correct |
188 ms |
472468 KB |
Output is correct |
8 |
Correct |
182 ms |
472240 KB |
Output is correct |
9 |
Correct |
183 ms |
472260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
342 ms |
476632 KB |
Output is correct |
2 |
Correct |
257 ms |
480440 KB |
Output is correct |
3 |
Correct |
553 ms |
475516 KB |
Output is correct |
4 |
Correct |
375 ms |
474436 KB |
Output is correct |
5 |
Correct |
471 ms |
475808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
179 ms |
472460 KB |
Output is correct |
2 |
Correct |
180 ms |
472484 KB |
Output is correct |
3 |
Correct |
195 ms |
472416 KB |
Output is correct |
4 |
Correct |
265 ms |
484900 KB |
Output is correct |
5 |
Correct |
273 ms |
484904 KB |
Output is correct |
6 |
Correct |
291 ms |
485024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
257 ms |
475608 KB |
Output is correct |
2 |
Correct |
266 ms |
475524 KB |
Output is correct |
3 |
Correct |
226 ms |
479648 KB |
Output is correct |
4 |
Correct |
221 ms |
474444 KB |
Output is correct |
5 |
Correct |
242 ms |
484932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
472256 KB |
Output is correct |
2 |
Correct |
180 ms |
472272 KB |
Output is correct |
3 |
Correct |
181 ms |
472260 KB |
Output is correct |
4 |
Correct |
181 ms |
472280 KB |
Output is correct |
5 |
Correct |
203 ms |
472252 KB |
Output is correct |
6 |
Correct |
176 ms |
472324 KB |
Output is correct |
7 |
Correct |
188 ms |
472468 KB |
Output is correct |
8 |
Correct |
182 ms |
472240 KB |
Output is correct |
9 |
Correct |
183 ms |
472260 KB |
Output is correct |
10 |
Correct |
260 ms |
475564 KB |
Output is correct |
11 |
Correct |
252 ms |
475588 KB |
Output is correct |
12 |
Correct |
227 ms |
479712 KB |
Output is correct |
13 |
Correct |
249 ms |
474456 KB |
Output is correct |
14 |
Correct |
225 ms |
484856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
200 ms |
473064 KB |
Output is correct |
2 |
Correct |
220 ms |
475540 KB |
Output is correct |
3 |
Correct |
221 ms |
475616 KB |
Output is correct |
4 |
Correct |
205 ms |
475528 KB |
Output is correct |
5 |
Correct |
193 ms |
474524 KB |
Output is correct |
6 |
Correct |
198 ms |
476824 KB |
Output is correct |
7 |
Correct |
203 ms |
479556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
472256 KB |
Output is correct |
2 |
Correct |
180 ms |
472272 KB |
Output is correct |
3 |
Correct |
181 ms |
472260 KB |
Output is correct |
4 |
Correct |
181 ms |
472280 KB |
Output is correct |
5 |
Correct |
203 ms |
472252 KB |
Output is correct |
6 |
Correct |
176 ms |
472324 KB |
Output is correct |
7 |
Correct |
188 ms |
472468 KB |
Output is correct |
8 |
Correct |
182 ms |
472240 KB |
Output is correct |
9 |
Correct |
183 ms |
472260 KB |
Output is correct |
10 |
Correct |
179 ms |
472460 KB |
Output is correct |
11 |
Correct |
180 ms |
472484 KB |
Output is correct |
12 |
Correct |
195 ms |
472416 KB |
Output is correct |
13 |
Correct |
265 ms |
484900 KB |
Output is correct |
14 |
Correct |
273 ms |
484904 KB |
Output is correct |
15 |
Correct |
291 ms |
485024 KB |
Output is correct |
16 |
Correct |
260 ms |
475564 KB |
Output is correct |
17 |
Correct |
252 ms |
475588 KB |
Output is correct |
18 |
Correct |
227 ms |
479712 KB |
Output is correct |
19 |
Correct |
249 ms |
474456 KB |
Output is correct |
20 |
Correct |
225 ms |
484856 KB |
Output is correct |
21 |
Correct |
222 ms |
473216 KB |
Output is correct |
22 |
Correct |
297 ms |
475616 KB |
Output is correct |
23 |
Correct |
373 ms |
475772 KB |
Output is correct |
24 |
Correct |
466 ms |
475940 KB |
Output is correct |
25 |
Correct |
377 ms |
474532 KB |
Output is correct |
26 |
Correct |
391 ms |
477552 KB |
Output is correct |
27 |
Correct |
307 ms |
480032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
472256 KB |
Output is correct |
2 |
Correct |
180 ms |
472272 KB |
Output is correct |
3 |
Correct |
181 ms |
472260 KB |
Output is correct |
4 |
Correct |
181 ms |
472280 KB |
Output is correct |
5 |
Correct |
203 ms |
472252 KB |
Output is correct |
6 |
Correct |
176 ms |
472324 KB |
Output is correct |
7 |
Correct |
188 ms |
472468 KB |
Output is correct |
8 |
Correct |
182 ms |
472240 KB |
Output is correct |
9 |
Correct |
183 ms |
472260 KB |
Output is correct |
10 |
Correct |
342 ms |
476632 KB |
Output is correct |
11 |
Correct |
257 ms |
480440 KB |
Output is correct |
12 |
Correct |
553 ms |
475516 KB |
Output is correct |
13 |
Correct |
375 ms |
474436 KB |
Output is correct |
14 |
Correct |
471 ms |
475808 KB |
Output is correct |
15 |
Correct |
179 ms |
472460 KB |
Output is correct |
16 |
Correct |
180 ms |
472484 KB |
Output is correct |
17 |
Correct |
195 ms |
472416 KB |
Output is correct |
18 |
Correct |
265 ms |
484900 KB |
Output is correct |
19 |
Correct |
273 ms |
484904 KB |
Output is correct |
20 |
Correct |
291 ms |
485024 KB |
Output is correct |
21 |
Correct |
257 ms |
475608 KB |
Output is correct |
22 |
Correct |
266 ms |
475524 KB |
Output is correct |
23 |
Correct |
226 ms |
479648 KB |
Output is correct |
24 |
Correct |
221 ms |
474444 KB |
Output is correct |
25 |
Correct |
242 ms |
484932 KB |
Output is correct |
26 |
Correct |
260 ms |
475564 KB |
Output is correct |
27 |
Correct |
252 ms |
475588 KB |
Output is correct |
28 |
Correct |
227 ms |
479712 KB |
Output is correct |
29 |
Correct |
249 ms |
474456 KB |
Output is correct |
30 |
Correct |
225 ms |
484856 KB |
Output is correct |
31 |
Correct |
200 ms |
473064 KB |
Output is correct |
32 |
Correct |
220 ms |
475540 KB |
Output is correct |
33 |
Correct |
221 ms |
475616 KB |
Output is correct |
34 |
Correct |
205 ms |
475528 KB |
Output is correct |
35 |
Correct |
193 ms |
474524 KB |
Output is correct |
36 |
Correct |
198 ms |
476824 KB |
Output is correct |
37 |
Correct |
203 ms |
479556 KB |
Output is correct |
38 |
Correct |
222 ms |
473216 KB |
Output is correct |
39 |
Correct |
297 ms |
475616 KB |
Output is correct |
40 |
Correct |
373 ms |
475772 KB |
Output is correct |
41 |
Correct |
466 ms |
475940 KB |
Output is correct |
42 |
Correct |
377 ms |
474532 KB |
Output is correct |
43 |
Correct |
391 ms |
477552 KB |
Output is correct |
44 |
Correct |
307 ms |
480032 KB |
Output is correct |
45 |
Correct |
215 ms |
473144 KB |
Output is correct |
46 |
Correct |
304 ms |
475692 KB |
Output is correct |
47 |
Correct |
381 ms |
475972 KB |
Output is correct |
48 |
Correct |
497 ms |
475848 KB |
Output is correct |
49 |
Correct |
374 ms |
474432 KB |
Output is correct |
50 |
Correct |
371 ms |
477404 KB |
Output is correct |
51 |
Correct |
322 ms |
479972 KB |
Output is correct |