#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define int long long
struct node{
int mx;
int left;
int right;
int delta;
node(){
mx = delta = 0;
left = right = -1;
}
};
node free_node;
int k;
struct Dynamic_Segment_Tree{
vector<node> t;
Dynamic_Segment_Tree(){
t.push_back(free_node);
}
int left_side(int v){
if(t[v].left == -1){
t[v].left = t.size();
t.push_back(free_node);
t.back().mx = t[v].mx;
}
return t[v].left;
}
int right_side(int v){
if(t[v].right == -1){
t[v].right = t.size();
t.push_back(free_node);
t.back().mx = t[v].mx;
}
return t[v].right;
}
void set(int v, int l, int r, int id, int w){
if(r < id || t[v].mx >= w) return;
if(t[v].delta){
if(t[v].left != -1){
t[left_side(v)].mx = max(t[left_side(v)].mx, t[v].mx);
t[right_side(v)].mx = max(t[right_side(v)].mx, t[v].mx);
t[left_side(v)].delta += t[v].delta;
t[right_side(v)].delta += t[v].delta;
}
t[v].mx += t[v].delta;
t[v].delta = 0;
}
if(l >= id){
t[v].mx = max(t[v].mx, w);
return;
}
int m = (l + r) >> 1;
set(right_side(v), m+1, r, id, w);
set(left_side(v), l, m, id, w);
}
void set(int id, int w){
set(0, 1, k, id, w);
}
int get(int v, int l, int r, int id){
if(v == -1 || r < id || l > id) return 0;
if(l == r) return t[v].mx + t[v].delta;
int m = (l + r) / 2;
return max({t[v].mx, get(t[v].left, l, m, id), get(t[v].right, m+1, r, id)}) + t[v].delta;
}
int get(int x){
return get(0, 1, k, x);
}
void merge(int v, int l, int r, Dynamic_Segment_Tree&d, int vd){
if(vd == -1) return;
if(d.t[vd].left == -1){
t[v].delta += d.t[vd].mx + d.t[vd].delta;
return;
}
int m = (l + r) / 2;
d.t[d.t[vd].right].mx = max(d.t[d.t[vd].right].mx, d.t[vd].mx);
d.t[d.t[vd].left].mx = max(d.t[d.t[vd].left].mx, d.t[vd].mx);
d.t[d.t[vd].right].delta += d.t[vd].delta;
d.t[d.t[vd].left].delta += d.t[vd].delta;
d.t[vd].delta = 0;
set(right_side(v), m+1, r, m+1, t[v].mx);
merge(right_side(v), m+1, r, d, d.t[vd].right);
set(left_side(v), l, m, l, t[v].mx);
merge(left_side(v), l, m, d, d.t[vd].left);
}
void merge(Dynamic_Segment_Tree& d){
merge(0, 1, k, d, 0);
}
};
Dynamic_Segment_Tree free_seg_tree;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m >> k;
vector<int> seg_id(n, -1);
vector<Dynamic_Segment_Tree> seg_tree;
vector<vector<int> > g(n);
vector<pair<int, int> > q(n, make_pair(-1, -1));
for(int i = 2, f; i <= n; i ++){
cin >> f;
g[f-1].push_back(i-1);
}
for(int i = 0, v, d, w; i < m; i ++){
cin >> v >> d >> w;
q[v-1] = make_pair(d, w);
}
for(int u = n-1; u >= 0; u --){
if(g[u].empty()){
if(q[u].first == -1) continue;
seg_id[u] = seg_tree.size();
seg_tree.push_back(free_seg_tree);
seg_tree[seg_id[u]].set(q[u].first, q[u].second);
}
else{
sort(g[u].begin(), g[u].end(), [&](int r, int l){
if(seg_id[r] == -1) return false;
if(seg_id[l] == -1) return true;
return seg_tree[seg_id[r]].t.size() > seg_tree[seg_id[l]].t.size();
});
if(seg_id[g[u][0]] == -1){
if(q[u].first != -1) {
seg_id[u] = seg_tree.size();
seg_tree.push_back(free_seg_tree);
seg_tree[seg_id[u]].set(q[u].first, q[u].second);
}
}
else{
seg_id[u] = seg_id[g[u][0]];
for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
seg_tree[seg_id[u]].merge(seg_tree[seg_id[g[u][i]]]);
seg_tree[seg_id[u]].set(q[u].first, seg_tree[seg_id[u]].get(q[u].first) + q[u].second);
}
}
// cout << u + 1 << ' ' << seg_tree[seg_id[u]].get(k) << endl;
}
cout << seg_tree[seg_id[0]].get(k);
return 0;
}
Compilation message
magictree.cpp: In function 'int main()':
magictree.cpp:147:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
142 ms |
105104 KB |
Output is correct |
| 2 |
Correct |
74 ms |
48064 KB |
Output is correct |
| 3 |
Correct |
392 ms |
291836 KB |
Output is correct |
| 4 |
Correct |
232 ms |
170028 KB |
Output is correct |
| 5 |
Correct |
250 ms |
170580 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
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 |
63 ms |
16440 KB |
Output is correct |
| 5 |
Correct |
77 ms |
16468 KB |
Output is correct |
| 6 |
Correct |
88 ms |
16480 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
73 ms |
12720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
