#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;
node(){
mx = 0;
left = right = -1;
}
};
node free_node;
int k;
struct Dynamic_Segment_Tree{
set<pair<int, int> > t;
Dynamic_Segment_Tree(){
t.emplace(0, 0);
}
void set(int id, int w){
auto elem = t.lower_bound(make_pair(id+1, 0));
elem --;
w += elem->second;
if(elem->first == id) t.erase(elem);
t.emplace(id, w);
elem = t.lower_bound(make_pair(id, w));
while(true){
auto nxt = elem;
nxt ++;
if(nxt == t.end() || nxt->second > elem->second)
break;
t.erase(nxt);
}
}
void merge(Dynamic_Segment_Tree&d){
while(!d.t.empty()){
auto e = d.t.end();
e --;
set(e->first, e->second);
d.t.erase(e);
}
}
void print(){
cout << "----" << endl;
for(auto x:t) cout <<x.first << ' ' << x.second << endl;
cout << "----" << endl;
}
};
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 continue;
}
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]]]);
if(q[u].first != -1)
seg_tree[seg_id[u]].set(q[u].first, q[u].second);
}
}
// cout << u + 1 << endl;
// seg_tree[seg_id[u]].print();
}
cout << seg_tree[seg_id[0]].t.rbegin()->second;
return 0;
}
Compilation message
magictree.cpp:31:10: error: declaration of 'void Dynamic_Segment_Tree::set(long long int, long long int)' changes meaning of 'set' [-fpermissive]
31 | void set(int id, int w){
| ^~~
In file included from /usr/include/c++/10/set:61,
from magictree.cpp:7:
/usr/include/c++/10/bits/stl_set.h:94:11: note: 'set' declared here as 'class std::set<std::pair<long long int, long long int> >'
94 | class set
| ^~~
magictree.cpp: In function 'int main()':
magictree.cpp:103: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]
103 | for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
| ~~^~~~~~~~~~~~~
