// author : HuuHung
// 25.3.2024
#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second
#define ll long long
#define lb long double
#define pb push_back
#define vi vector <int>
#define vll vector <ll>
#define Bit(x, i) ((x) >> (i) & 1)
#define Mask(i) (1ll << (i))
#define All(v) (v).begin(), (v).end()
using namespace std;
void maxzi(int &a, int b){
a = max(a, b);
}
void minzi(int &a, int b){
a = min(a, b);
}
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;
void add(int &a, int b){
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int Pow(int a, int b){
if (b == 0) return 1;
if (b % 2) return 1ll * a * Pow(a, b - 1) % mod;
int c = Pow(a, b / 2);
return 1ll * c * c % mod;
}
// * end
struct Node {
Node *left, *right;
ll Max, lz;
Node (ll val){
left = nullptr;
right = nullptr;
Max = val;
lz = 0;
}
Node (Node *old, ll val){
this -> left = old -> left;
this -> right = old -> right;
this -> Max = old -> Max;
this -> lz = old -> lz;
this -> Max += val;
this -> lz += val;
}
Node (Node *left, Node *right, int lz){
this -> left = left;
this -> right = right;
this -> Max = max(left -> Max, right -> Max) + lz;
this -> lz = lz;
}
};
struct persis{
Node *ver[N];
Node *build(int l, int r){
if (l == r) return new Node(0);
int mid = l + r >> 1;
return new Node(build(l, mid), build(mid + 1, r), 0);
}
Node *update(Node *old, int l, int r, int u, int v, ll val){
if (u <= l && r <= v){
return new Node(old, val);
}
int mid = l + r >> 1;
if (old -> left == nullptr){
old -> left = new Node(old -> Max - old -> lz);
old -> right = new Node(old -> Max - old -> lz);
}
if (mid < u) return new Node(old -> left, update(old -> right, mid + 1, r, u, v, val), old -> lz);
if (mid + 1 > v) return new Node(update(old -> left, l, mid, u, v, val), old -> right, old -> lz);
return new Node(update(old -> left, l, mid, u, v, val), update(old -> right, mid + 1, r, u, v, val), old -> lz);
}
ll get(Node *cur, int l, int r, int u){
if (l > u) return 0ll;
if (r <= u) return cur -> Max;
if (cur -> left == nullptr){
return cur -> Max;
cur -> left = new Node(cur -> Max - cur -> lz);
cur -> right = new Node(cur -> Max - cur -> lz);
}
int mid = l + r >> 1;
return max(get(cur -> left, l, mid, u), get(cur -> right, mid + 1, r, u)) + cur -> lz;
}
int walk(Node *cur, int l, int r, ll val){
if (cur -> left == nullptr || l == r) {
if (cur -> Max > val) return l - 1;
else return l;
}
int mid = l + r >> 1;
val -= cur -> lz;
if (cur -> left -> Max < val) return walk(cur -> right, mid + 1, r, val);
return walk(cur -> left, l, mid, val);
}
Node *assign(Node *old, int l, int r, int u, int v, ll val){
if (u <= l && r <= v){
return new Node(val);
}
int mid = l + r >> 1;
if (old -> left == nullptr){
old -> left = new Node(old -> Max - old -> lz);
old -> right = new Node(old -> Max - old -> lz);
}
if (mid < u) return new Node(old -> left, update(old -> right, mid + 1, r, u, v, val), old -> lz);
if (mid + 1 > v) return new Node(update(old -> left, l, mid, u, v, val), old -> right, old -> lz);
return new Node(update(old -> left, l, mid, u, v, val), update(old -> right, mid + 1, r, u, v, val), old -> lz);
}
} ac;
int n, m, k;
vector <int> adj[N];
int d[N], w[N];
set <int> event[N];
void dfs(int u){
ac.ver[u] = ac.ver[0];
for (int v : adj[u]){
dfs(v);
if (event[u].size() < event[v].size()){
swap(event[u], event[v]);
swap(ac.ver[u], ac.ver[v]);
}
int last = 0;
for (auto x : event[v]){
event[u].insert(x);
if (!last){
last = x;
continue;
}
ac.ver[u] = ac.update(ac.ver[u], 1, k, last, x - 1, ac.get(ac.ver[v], 1, k, last));
last = x;
}
}
if (d[u]){
//cout << u << ' ' << d[u] << endl;
event[u].insert(d[u]);
ll val = ac.get(ac.ver[u], 1, k, d[u]) + w[u];
int pos = ac.walk(ac.ver[u], 1, k, val);
ac.ver[u] = ac.assign(ac.ver[u], 1, k, d[u], pos, val);
}
}
void solve(){
cin >> n >> m >> k;
for (int i = 2; i <= n; ++ i){
int p; cin >> p;
adj[p].pb(i);
}
for (int i = 1; i <= m; ++ i){
int v; cin >> v;
cin >> d[v] >> w[v];
}
for (int i = 1; i <= n; ++ i) event[i].insert(k + 1);
ac.ver[0] = ac.build(1, k);
//cout << ac.get(ac.ver[4], 1, k, k) << endl;
dfs(1);
cout << ac.get(ac.ver[1], 1, k, k);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t --) solve();
return 0;
}
Compilation message
magictree.cpp: In member function 'Node* persis::build(int, int)':
magictree.cpp:79:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | int mid = l + r >> 1;
| ~~^~~
magictree.cpp: In member function 'Node* persis::update(Node*, int, int, int, int, long long int)':
magictree.cpp:88:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | int mid = l + r >> 1;
| ~~^~~
magictree.cpp: In member function 'long long int persis::get(Node*, int, int, int)':
magictree.cpp:107:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
107 | int mid = l + r >> 1;
| ~~^~~
magictree.cpp: In member function 'int persis::walk(Node*, int, int, long long int)':
magictree.cpp:117:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
117 | int mid = l + r >> 1;
| ~~^~~
magictree.cpp: In member function 'Node* persis::assign(Node*, int, int, int, int, long long int)':
magictree.cpp:128:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
128 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
294 ms |
212052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
17752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
904 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
28252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
