#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 2e5 + 10;
int a[N], ans[N], sz[N], in[N], ou[N], timer = 0, used[N], b[N], laz[N * 4], seg[N * 4], val[N], k;
vector <int> ed[N];
stack <int> action;
void rollback() {
while (sz(action)) {
int t = action.top();
laz[t] = seg[t] = 0;
action.pop();
}
}
void dfs(int u) {
sz[u] = 1;
timer++;
in[u] = timer;
b[timer] = a[u];
for (auto x : ed[u]) {
dfs(x);
sz[u] += sz[x];
}
ou[u] = timer;
}
void push(int id) {
int t = laz[id];
laz[id * 2] += t;
laz[id * 2 + 1] += t;
seg[id * 2] += t;
seg[id * 2 + 1] += t;
action.push(id * 2);
action.push(id * 2 + 1);
laz[id] = 0;
}
void add(int id, int l, int r, int u, int v, int c) {
if (l > v || r < u || u > v)
return;
if (l >= u && r <= v) {
action.push(id);
laz[id] += c;
seg[id] += c;
return;
}
action.push(id);
push(id);
int m = (l + r) / 2;
add(id * 2, l, m, u, v, c);
add(id * 2 + 1, m + 1, r, u, v, c);
seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}
void upd(int id, int l, int r, int p, int v) {
if (l > p || r < p)
return;
if (l == r) {
seg[id] = max(seg[id], v);
return;
}
push(id);
action.push(id);
int m = (l + r) / 2;
upd(id * 2, l, m, p, v);
upd(id * 2 + 1, m + 1, r, p, v);
seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v) {
if (l > v || r < u || u > v)
return 0;
if (l >= u && r <= v)
return seg[id];
action.push(id);
push(id);
int m = (l + r) / 2;
return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}
vector <pair <int, int>> save[N];
void dfs2(int u, bool is) {
int mx = 0;
for (auto x : ed[u]) {
if (sz[x] > sz[mx])
mx = x;
}
for (auto x : ed[u]) {
if (x != mx) {
dfs2(x, 0);
}
}
if (mx)
dfs2(mx, 1);
for (auto x : ed[u]) {
if (x != mx) {
vector < vector <int>> seg;
vector <pair <int, int>> point;
int lst = 1, mx = 0;
for (auto t : save[x]) {
seg.pb({lst, t.f, mx});
point.pb({t.f, get(1, 1, k, 1, t.f) + t.s});
lst = t.f;
mx = max(mx, t.s);
}
seg.pb({lst, k, mx});
for (auto x : seg) {
add(1, 1, k, x[0], x[1], x[2]);
}
for (auto x : point) {
upd(1, 1, k, x.f, x.s);
}
}
}
int all = get(1, 1, k, 1, a[u]) + val[u];
int v = get(1, 1, k, a[u], a[u]);
if (all > v) {
add(1, 1, k, a[u], a[u], all - v);
}
if (u == 1)
ans[u] = get(1, 1, k, 1, k);
if (is == 0) {
for (int i = in[u]; i <= ou[u]; i++) {
if (used[b[i]])
continue;
int cnt = get(1, 1, k, b[i], b[i]);
save[u].pb({b[i], cnt});
used[b[i]] = 1;
}
for (int i = in[u]; i <= ou[u]; i++) {
used[b[i]] = 0;
}
rollback();
sort(all(save[u]));
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m >> k;
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
ed[x].pb(i);
}
for (int i = 0; i < m; i++) {
int v, d, w;
cin >> v >> d >> w;
a[v] = d;
val[v] = w;
}
dfs(1);
dfs2(1, 1);
cout << ans[1] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
317 ms |
40372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 2 |
Correct |
4 ms |
15452 KB |
Output is correct |
| 3 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 4 |
Correct |
158 ms |
104636 KB |
Output is correct |
| 5 |
Correct |
150 ms |
104700 KB |
Output is correct |
| 6 |
Correct |
168 ms |
104696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
19276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
20572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
