// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using ll = long long;
using vl = V<ll>;
struct Seg {
const ll ID = 0, IDL = -1; ll comb(ll a, ll b) { return max(a, b); }
int n; vl seg, lazy; void init(int _n) {
n = 1; while(n < _n) n *= 2;
seg.assign(2 * n, ID); lazy.assign(2 * n, IDL);
}
void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }
void push(int x, int L, int R) {
if (lazy[x] != IDL) {
seg[x] = lazy[x];
if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] = lazy[x];
lazy[x] = IDL;
}
}
void upd(int l, int r, ll v, int x, int L, int R) {
push(x, L, R); if (r < L || R < l) return;
if (L <= l && r <= R) {
lazy[x] = v; push(x, L, R); return;
}
int M = (L + R) / 2;
upd(l, r, v, 2 * x, L, M);
upd(l, r, v, 2 * x + 1, M + 1, R);
}
ll query(int l, int r, int x, int L, int R) {
push(x, L, R); if (r < L || R < l) return ID;
if (L <= l && r <= R) return seg[x];
int M = (L + R) / 2;
return comb(
query(l, r, 2 * x, L, M),
query(l, r, 2 * x + 1, M + 1, R)
);
}
void upd(int l, int r, ll v) { upd(l, r, v, 1, 0, n - 1); }
ll query(int l, int r) { return query(l, r, 1, 0, n - 1); }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M, K; cin >> N >> M >> K;
// (euler tour + segment tree + offline queries)? to compute dp
// then basic tree dp with dp values to get answer
V<vi> chd(N); for(int u = 1; u < N; u++) {
int p; cin >> p; --p;
chd[p].pb(u);
}
vi st(N), en(N); int t = 0;
function<void(int)> gen = [&](int u) {
st[u] = t++;
for(auto& v : chd[u]) gen(v);
en[u] = t - 1;
};
gen(0);
V<array<int, 3>> E;
for(int i = 0; i < M; i++) {
int v, d, w; cin >> v >> d >> w; --v, --d;
E.push_back({d, v, w});
}
sort(begin(E), end(E), [&](auto x, auto y) {
if (x[0] == y[0]) return st[x[1]] < st[y[1]];
return x[0] < y[0];
});
Seg T; T.init(N);
vl dp(N);
for(auto q : E) {
auto [d, u, w] = q;
// cout << d << " " << u << endl;
int best = 0;
for(auto& v : chd[u]) best += T.query(st[v], en[v]);
dp[u] = best + w;
T.upd(st[u] + 1, en[u], 0);
T.upd(st[u], st[u], dp[u]);
// cout << u << " " << w << " " << best << endl;
}
function<ll(int)> ans = [&](int u) {
ll best = 0;
for(auto& v : chd[u]) best += ans(v);
return max(best, dp[u]);
};
cout << ans(0) << nl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
10172 KB |
Output is correct |
| 2 |
Correct |
24 ms |
15240 KB |
Output is correct |
| 3 |
Correct |
43 ms |
12564 KB |
Output is correct |
| 4 |
Correct |
36 ms |
12292 KB |
Output is correct |
| 5 |
Correct |
47 ms |
13520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
11116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
