#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;
const int MAXN=2e5+10;
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], kopie[MAXN], cnt;
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=min(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;
int maxind=-1;
for (int i=0;i<v[x].size();i++) {
find_ss(v[x][i]);
ss[x]+=ss[v[x][i]];
if (maxind==-1 || ss[v[x][i]]>ss[v[x][maxind]]) maxind=i;
}
if (maxind!=-1) swap(v[x][0],v[x][maxind]);
}
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;
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());
int k=0;
for (auto j:vals[v[x][i]]) {
dp[v[x][i]][k]=query(1,1,cnt,j);
k++;
}
auto it=vals[v[x][i]].lower_bound(h[x]);
cur_res+=query(1,1,cnt,(*it));
set_update(1,1,cnt,1,cnt,0);
}
find_dp(v[x][0]);
for (auto it=vals[v[x][0]].begin();it!=vals[v[x][0]].end();it++) vals[x].insert((*it));
auto it=vals[v[x][0]].lower_bound(h[x]);
cur_res+=query(1,1,cnt,(*it));
for (int i=1;i<v[x].size();i++) {
for (auto j:vals[v[x][i]]) {
auto it=vals[x].lower_bound(j);
set_update(1,1,cnt,j,j, query(1,1,cnt,(*it)) );
}
}
for (int i=1;i<v[x].size();i++) {
int 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 {
auto pr=it;
pr--;
add_update(1,1,cnt,(*pr)+1,(*it),dp[v[x][i]][k]);
}
vals[x].insert((*it));
}
}
vals[x].insert(h[x]);
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);
}
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, par;
cin >> n;
for (int i=1;i<=n;i++) {
cin >> par >> h[i] >> c[i];
if (i!=1) v[par].push_back(i);
kopie[i]=h[i];
}
sort(kopie+1,kopie+n+1);
cnt=1;
for (int i=1;i<=n;i++) {
if (um[kopie[i]]==0) {
um[kopie[i]]=cnt;
cnt++;
}
}
cnt++;
for (int i=1;i<=n;i++) h[i]=um[h[i]];
find_ss(1);
for (int j=1;j<=4*(n+1);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: In function 'void find_ss(int)':
worst_reporter2.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i=0;i<v[x].size();i++) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'void find_dp(int)':
worst_reporter2.cpp:115:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int i=1;i<v[x].size();i++) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | 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++) {
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
25180 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
7 ms |
25268 KB |
Output is correct |
| 4 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 5 |
Incorrect |
31 ms |
30284 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
25180 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
7 ms |
25268 KB |
Output is correct |
| 4 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 5 |
Incorrect |
31 ms |
30284 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
25180 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
7 ms |
25268 KB |
Output is correct |
| 4 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 5 |
Incorrect |
31 ms |
30284 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
