#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("avx2")
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;
template <typename T>
using prq = priority_queue <T>;
template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;
template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }
typedef struct node* pnode;
struct node{
pnode l, r;
ll s, p;
node(ll s = 0, ll p = 0): s(s), p(p) { l = r = nullptr; }
void apply(ll x){
umax(s, x), umax(p, x);
}
void push(){
if (!l) l = new node;
if (!r) r = new node;
if (!p) return;
l->apply(p), r->apply(p);
p = 0;
}
void pull(){
if (l) umax(s, l->s);
if (r) umax(s, r->s);
}
bool leaf(){
return !l && !r;
}
};
void upd(int l, int r, ll x, int tl, int tr, pnode v){
if (l >= r) return;
if (tl == l && tr == r) return void(v->apply(x));
v->push();
int tm = tl + tr >> 1;
upd(l, min(tm, r), x, tl, tm, v->l);
upd(max(l, tm), r, x, tm, tr, v->r);
v->pull();
}
ll get(int p, int tl, int tr, pnode v){
if (tl + 1 == tr) return v->s;
v->push();
int tm = tl + tr >> 1;
if (p < tm) return get(p, tl, tm, v->l);
return get(p, tm, tr, v->r);
}
void mrg(pnode &v1, pnode v2){
// cout << "+\n";
if (!v1 || !v2) return void(v1 = v1 ? v1 : v2);
if (v1->leaf()){
// cout << "v1 LEAF\n";
v1->s += v2->s;
v1->p += v2->p;
v1->l = v2->l, v1->r = v2->r;
}
else if (!v2->leaf()){
v1->push(), v2->push();
mrg(v1->l, v2->l), mrg(v1->r, v2->r);
}
else{
// cout << "v2 LEAF\n";
v1->s += v2->s;
v1->p += v2->p;
}
delete v2;
v1->pull();
}
void dbg(int l, int r, pnode v){
if (!v){
for (int i = l; i < r; ++i){
cout << "0 ";
}
return;
}
if (l + 1 == r) return void(cout << v->s << " ");
v->push();
int m = l + r >> 1;
dbg(l, m, v->l), dbg(m, r, v->r);
}
inline int solve(){
int n, m, k;
cin >> n >> m >> k;
vec <vec <int>> g(n);
for (int i = 1; i < n; ++i){
int p; cin >> p, --p;
g[p].push_back(i);
}
vec <int> d(n, -1), w(n);
for (int i = 0; i < m; ++i){
int u, x, y;
cin >> u >> x >> y, --u, --x;
d[u] = x, w[u] = y;
}
{
vec <pnode> dp(n);
auto dfs = [&](auto &&dfs, int u) -> void{
dp[u] = new node;
for (auto &v: g[u]){
dfs(dfs, v);
mrg(dp[u], dp[v]);
}
// cout << u + 1 << ":\n";
// cout << " Before: ";
// dbg(0, k, dp[u]);
// cout << "\n";
if (~d[u]){
ll nw = get(d[u], 0, k, dp[u]) + w[u];
// cout << " upd " << d[u] << " " << k - 1 << " with " << nw << "\n";
upd(d[u], k, nw, 0, k, dp[u]);
}
// cout << " After: ";
// dbg(0, k, dp[u]);
// cout << "\n";
};
dfs(dfs, 0);
cout << dp[0]->s << "\n";
}
// cout << "\n";
// {
// vec <vec <ll>> dp(n, vec <ll> (k));
// auto dfs = [&](auto &&dfs, int u) -> void{
// for (auto &v: g[u]){
// dfs(dfs, v);
// for (int i = 0; i < k; ++i){
// dp[u][i] += dp[v][i];
// }
// }
// cout << u + 1 << ":\n";
// cout << " Before: ";
// for (int i = 0; i < k; ++i){
// cout << dp[u][i] << " ";
// }
// cout << "\n";
// if (~d[u]){
// ll nw = dp[u][d[u]] + w[u];
// cout << "upd " << d[u] << " " << k - 1 << " with " << nw << "\n";
// for (int i = d[u]; i < k; ++i){
// umax(dp[u][i], nw);
// }
// }
// cout << " After: ";
// for (int i = 0; i < k; ++i){
// cout << dp[u][i] << " ";
// }
// cout << "\n";
// };
// dfs(dfs, 0);
// cout << *max_element(all(dp[0]));
// };
return 0;
}
inline void precalc(){}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tst = 1; //cin >> tst;
precalc();
while(tst--) solve();
return 0;
}
Compilation message
magictree.cpp: In function 'void upd(int, int, ll, int, int, pnode)':
magictree.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int tm = tl + tr >> 1;
| ~~~^~~~
magictree.cpp: In function 'll get(int, int, int, pnode)':
magictree.cpp:72:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int tm = tl + tr >> 1;
| ~~~^~~~
magictree.cpp: In function 'void dbg(int, int, pnode)':
magictree.cpp:108:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
108 | int m = l + r >> 1;
| ~~^~~
| # |
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 |
76 ms |
13744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
56 ms |
22352 KB |
Output is correct |
| 5 |
Correct |
69 ms |
22380 KB |
Output is correct |
| 6 |
Correct |
81 ms |
23380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
5840 KB |
Output is correct |
| 2 |
Correct |
38 ms |
5856 KB |
Output is correct |
| 3 |
Correct |
46 ms |
11084 KB |
Output is correct |
| 4 |
Correct |
28 ms |
4756 KB |
Output is correct |
| 5 |
Correct |
36 ms |
18224 KB |
Output is correct |
| # |
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 |
5 ms |
1964 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 |
- |
