#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(v) int(v.size())
#define ar array
const int N = 1e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
struct T {
T *l, *r;
ll sum;
T() {
l = r = nullptr;
sum = 0;
}
void upd(int tl, int tr, int pos, ll x) {
sum += x;
if (tl == tr) {
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) {
if (!l) l = new T();
l->upd(tl, tm, pos, x);
} else {
if (!r) r = new T();
r->upd(tm+1, tr, pos, x);
}
}
ll qry(int tl, int tr, int ql, int qr) {
if (qr < tl || ql > tr) return 0;
if (ql <= tl && tr <= qr) {
return sum;
}
int tm = (tl + tr) / 2;
return (l ? l->qry(tl, tm, ql, qr) : 0) + (r ? r->qry(tm+1, tr, ql, qr) : 0);
}
};
const int BASE = 1e9+20;
void upd(T* tree, int l, int r, ll x) {
tree->upd(0, BASE, l, +x);
tree->upd(0, BASE, r+1, -x);
}
ll qry(T* tree, int pos) {
return tree->qry(0, BASE, 0, pos);
}
struct S {
// i must be >= the max
map<int, ll> mp;
T* tree;
S() {
mp[0] = 0;
tree = new T();
}
void add_range(int l, int r, ll x) {
upd(tree, l, r, x);
/*
for (auto& [k, v] : mp) {
if (l <= k && k <= r) {
v += x;
}
}
*/
}
void merge(S& nxt) {
if (sz(mp) < sz(nxt.mp)) {
swap(mp, nxt.mp);
swap(tree, nxt.tree);
}
for (auto [k, v] : nxt.mp) {
auto it = --mp.upper_bound(k);
ll use = it->second + qry(tree, it->first);
mp[k] = use - qry(tree, k);
}
for (auto one = nxt.mp.begin(); one != nxt.mp.end(); one++) {
auto two = next(one);
if (two == nxt.mp.end()) {
// one->first, to the end
add_range(one->first, MOD, one->second);
} else {
// one->first, two->first-1
add_range(one->first, two->first - 1, one->second);
}
}
}
void add(int t, int x) {
auto base = --mp.upper_bound(t);
ll cur = base->second + qry(tree, base->first) + x;
auto it = mp.lower_bound(t);
while (it != mp.end() && it->second + qry(tree, it->first) <= cur) {
mp.erase(it);
it = mp.lower_bound(t);
}
mp[t] = cur - qry(tree, t);
}
ll get_ans() {
auto it = prev(mp.end());
return it->second + qry(tree, it->first);
}
} s[N];
int n, m, k;
vector<int> adj[N];
int t[N], a[N];
// value of ancestor has to be >= value of any thing in the subtree
void dfs(int c, int p) {
s[c] = S();
for (int nxt : adj[c]) if (nxt != p) {
dfs(nxt, c);
s[c].merge(s[nxt]);
}
if (t[c] != -1) s[c].add(t[c], a[c]);
}
void solve() {
cin >> n >> m >> k;
for (int i = 1; i < n; i++) {
int p; cin >> p, --p;
adj[p].push_back(i);
}
memset(t, -1, sizeof(t));
memset(a, -1, sizeof(a));
while (m--) {
int c, i, x; cin >> c >> i >> x, --c;
t[c] = i, a[c] = x;
}
dfs(0, -1);
cout << s[0].get_ans() << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
18260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
266 ms |
123156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
18456 KB |
Output is correct |
| 2 |
Correct |
13 ms |
18488 KB |
Output is correct |
| 3 |
Correct |
13 ms |
18516 KB |
Output is correct |
| 4 |
Correct |
112 ms |
40472 KB |
Output is correct |
| 5 |
Correct |
129 ms |
44440 KB |
Output is correct |
| 6 |
Correct |
131 ms |
40528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
196 ms |
77760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
18260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
37196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
18260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
18260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
