#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e5 + 10;
vector<int> T[N];
struct Node{
ll val;
ll lazy;
};
Node G[N * 4 + 512];
void push(int node, int cl, int cr){
G[node].val += G[node].lazy;
if(cl != cr){
G[node * 2].lazy += G[node].lazy;
G[node * 2 + 1].lazy += G[node].lazy;
}
G[node].lazy = 0;
}
void upd(int node, int cl, int cr, int tl, int tr, ll v){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
G[node].lazy = v;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
upd(node * 2, cl, mid, tl, tr, v);
upd(node * 2 + 1, mid + 1, cr, tl, tr, v);
G[node].val = max(G[node * 2].val, G[node * 2 + 1].val);
}
ll get(int node, int cl, int cr, int tl, int tr){
push(node, cl, cr);
if(cr < tl || cl > tr)
return 0ll;
if(cl >= tl && cr <= tr){
return G[node].val;
}
int mid = (cl + cr) / 2;
return max(get(node * 2, cl, mid, tl, tr), get(node * 2 + 1, mid + 1, cr, tl, tr));
}
int k;
int sub[N];
void dfs(int u){
sub[u] = 1;
for(auto x : T[u]){
dfs(x);
sub[u] += sub[x];
}
}
set<int> ff[N];
set<pii> res[N];
int tr[N], ww[N];
struct R{
int lef;
int rig;
ll ch;
};
vector<R> rev[N];
void dfs1(int u, bool keep){
int id = -1;
for(auto x : T[u]){
if(id == -1 || sub[x] > sub[id])
id = x;
}
for(auto x : T[u]){
if(x != id){
dfs1(x, false);
for(auto y : ff[x]){
ff[u].insert(y);
}
ff[x].clear();
}
}
if(id != -1){
dfs1(id, true);
swap(ff[u], ff[id]);
for(auto y : ff[id]){
ff[u].insert(y);
}
ff[id].clear();
swap(rev[u], rev[id]);
}
for(auto x : T[u]){
if(x != id){
int las = 0;
ll cv = -1;
for(auto y : res[x]){
if(las != 0){
upd(1, 1, k, las, y.fi - 1, y.se);
rev[u].push_back({las, y.fi - 1, y.se});
}
las = y.fi;
cv = y.se;
}
if(las != 0){
upd(1, 1, k, las, k, cv);
rev[u].push_back({las, k, cv});
}
}
}
if(tr[u] > 0){
ff[u].insert(tr[u]);
auto it = ff[u].lower_bound(tr[u]);
ll upd_val = get(1, 1, k, tr[u], tr[u]) + ww[u];
int en;
ll cur;
int st;
while(it != ff[u].end()){
st = (*it);
cur = get(1, 1, k, st, st);
if(upd_val > cur){
auto nx = ff[u].erase(it);
if(nx == ff[u].end())
en = k;
else
en = (*nx) - 1;
upd(1, 1, k, st, en, upd_val - cur);
rev[u].push_back({st, en, upd_val - cur});
it = nx;
}
else{
break;
}
}
ff[u].insert(tr[u]);
}
if(!keep){
for(auto x : ff[u]){
res[u].insert(mp(x, get(1, 1, k, x, x)));
}
for(auto f : rev[u]){
upd(1, 1, k, f.lef, f.rig, -f.ch);
}
rev[u].clear();
}
}
vector<ll> sol[N];
void brute(int x){
sol[x].resize(k);
for(auto p : T[x]){
brute(p);
for(int t = 0;t < k ;t ++ )
sol[x][t] += sol[p][t];
}
if(tr[x] == 0) return;
int ts = tr[x] - 1;
int vl = sol[x][ts] + ww[x];
for(int j = ts; j < k ; j ++ ){
sol[x][j] = max(sol[x][j], vl);
}
}
int main(){
fastIO;
int n, m;
cin >> n >> m >> k;
int p;
for(int i = 2; i <= n; i ++ ){
cin >> p;
T[p].push_back(i);
}
int id;
for(int i = 1; i <= m ; i ++ ){
cin >> id >> tr[id] >> ww[id];
}
dfs(1);
dfs1(1, true);
brute(1);
cout << sol[1][k-1] << "\n";
return 0;
}
Compilation message
magictree.cpp: In function 'void brute(int)':
magictree.cpp:173:38: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&, int&)'
173 | sol[x][j] = max(sol[x][j], vl);
| ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from magictree.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
222 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: template argument deduction/substitution failed:
magictree.cpp:173:38: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
173 | sol[x][j] = max(sol[x][j], vl);
| ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from magictree.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
268 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: template argument deduction/substitution failed:
magictree.cpp:173:38: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
173 | sol[x][j] = max(sol[x][j], vl);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from magictree.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3456 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: template argument deduction/substitution failed:
magictree.cpp:173:38: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
173 | sol[x][j] = max(sol[x][j], vl);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from magictree.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3462 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: template argument deduction/substitution failed:
magictree.cpp:173:38: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
173 | sol[x][j] = max(sol[x][j], vl);
| ^
