#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int MAXN=2e5+3;
#define endl '\n'
#define getchar getchar_unlocked
struct Node {
long long mx, lazyadd, lazyset;
};
vector <int> v[MAXN];
set <int> vals[MAXN];
vector <long long> dp[MAXN];
Node tree[4*MAXN];
long long c[MAXN];
int h[MAXN], cnt;
pair <int,int> kopie[MAXN];
int ss[MAXN];
unordered_map <int,int> um;
void merge_lazy(int par, int ch) {
if (tree[par].lazyset!=-1) {
tree[ch].lazyset=tree[par].lazyset;
tree[ch].lazyadd=0;
return;
}
if (tree[ch].lazyset==-1) tree[ch].lazyadd+=tree[par].lazyadd;
else tree[ch].lazyset+=tree[par].lazyadd;
}
void push_lazy(int node, int l, int r) {
if (tree[node].lazyadd==0 && tree[node].lazyset==-1) return;
if (tree[node].lazyadd==0) tree[node].mx=tree[node].lazyset;
else tree[node].mx+=tree[node].lazyadd;
if (l!=r) {
merge_lazy(node,node*2);
merge_lazy(node,node*2+1);
}
tree[node].lazyadd=0;
tree[node].lazyset=-1;
}
void add_update(int node, int l, int r, int ql, int qr, long long ch) {
push_lazy(node,l,r);
if (ql>r || qr<l) return;
if (l>=ql && r<=qr) {
tree[node].lazyadd=ch;
push_lazy(node,l,r);
return;
}
int mid=(l+r)/2;
add_update(node*2,l,mid,ql,qr,ch);
add_update(node*2+1,mid+1,r,ql,qr,ch);
tree[node].mx=max(tree[node*2].mx,tree[node*2+1].mx);
}
void set_update(int node, int l, int r, int ql, int qr, long long ch) {
push_lazy(node,l,r);
if (ql>r || qr<l) return;
if (l>=ql && r<=qr) {
tree[node].lazyset=ch;
push_lazy(node,l,r);
return;
}
int mid=(l+r)/2;
set_update(node*2,l,mid,ql,qr,ch);
set_update(node*2+1,mid+1,r,ql,qr,ch);
tree[node].mx=max(tree[node*2].mx,tree[node*2+1].mx);
}
long long query(int node, int l, int r, int qind) {
push_lazy(node,l,r);
if (l==r) return tree[node].mx;
int mid=(l+r)/2;
if (qind<=mid) return query(node*2,l,mid,qind);
return query(node*2+1,mid+1,r,qind);
}
int find_ind(int node, int l, int r, int ql, int qr, long long ch) {
push_lazy(node,l,r);
if (ql>r || qr<l || tree[node].mx<=ch) return -1;
if (l==r) return l;
int mid=(l+r)/2;
int res=find_ind(node*2,l,mid,ql,qr,ch);
if (res!=-1) return res;
return find_ind(node*2+1,mid+1,r,ql,qr,ch);
}
void find_ss(int x) {
ss[x]=1;
for (int i=0;i<v[x].size();++i) {
find_ss(v[x][i]);
ss[x]+=ss[v[x][i]];
}
for (int i=1;i<v[x].size();++i) {
if (ss[v[x][i]]>ss[v[x][0]]) swap(v[x][0],v[x][i]);
}
}
void find_dp(int x) {
if (v[x].empty()) {
add_update(1,1,cnt,h[x]+1,cnt,c[x]);
vals[x].insert(h[x]);
vals[x].insert(cnt);
return;
}
long long cur_res;
int k;
cur_res=0;
for (int i=1;i<v[x].size();++i) {
find_dp(v[x][i]);
dp[v[x][i]].resize(vals[v[x][i]].size());
k=0;
for (auto j:vals[v[x][i]]) {
dp[v[x][i]][k]=query(1,1,cnt,j);
k++;
}
cur_res+=query(1,1,cnt,(*vals[v[x][i]].lower_bound(h[x])));
set_update(1,1,cnt,1,cnt,0);
}
find_dp(v[x][0]);
vals[x]=move(vals[v[x][0]]);
cur_res+=query(1,1,cnt,(*vals[x].lower_bound(h[x])));
for (int i=1;i<v[x].size();++i) {
for (auto j:vals[v[x][i]]) {
set_update(1,1,cnt,j,j, query(1,1,cnt,(*vals[x].lower_bound(j))) );
}
}
for (int i=1;i<v[x].size();++i) {
k=0;
for (auto it=vals[v[x][i]].begin();it!=vals[v[x][i]].end();it++,k++) {
if (k==0) add_update(1,1,cnt,1,(*it),dp[v[x][i]][k]);
else {
add_update(1,1,cnt,(*prev(it))+1,(*it),dp[v[x][i]][k]);
}
vals[x].insert((*it));
}
}
add_update(1,1,cnt,1,cnt,c[x]);
int pos=find_ind(1,1,cnt,1,h[x],cur_res);
if (pos!=-1) {
set_update(1,1,cnt,pos,h[x],cur_res);
}
vals[x].insert(h[x]);
}
int read() {
int res=0;
char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') {
res=res*10+c-'0';
c=getchar();
}
return res;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, par;
n=read();
for (int i=1;i<=n;++i) {
par=read();
h[i]=read();
c[i]=read();
if (i!=1) v[par].push_back(i);
kopie[i].first=h[i];
kopie[i].second=i;
}
sort(kopie+1,kopie+n+1);
cnt=0;
for (int i=1;i<=n;++i) {
if (kopie[i].first!=kopie[i-1].second) cnt++;
h[kopie[i].second]=cnt;
}
cnt++;
find_ss(1);
for (int j=1;j<=4*cnt;++j) {
tree[j].lazyset=-1;
}
find_dp(1);
cout << query(1,1,cnt,1) << endl;
return 0;
}
/*
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
*/
Compilation message
worst_reporter2.cpp:20:1: error: 'unordered_map' does not name a type
20 | unordered_map <int,int> um;
| ^~~~~~~~~~~~~
worst_reporter2.cpp: In function 'void find_ss(int)':
worst_reporter2.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int i=0;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i=1;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'void find_dp(int)':
worst_reporter2.cpp:118:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for (int i=1;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp:137:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int i=1;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for (int i=1;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
