#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=2e5+1;
const ll inf=1e18;
vec<int> g[N];
int c[N],a[N],h[N];
struct fenwick{
ll fnw[N];
fenwick(){
fill(fnw,fnw+N,0);
}
void upd(int i,ll x){
++i;
while(i<N){
fnw[i]+=x;
i+=i&-i;
}
}
ll get(int i){
++i;
ll ans=0;
while(i>0){
ans+=fnw[i];
i-=i&-i;
}
return ans;
}
}fen;
map<int,ll> mp;
vec<pil> *dps[N];
int dp[N];
void dfs1(int v){
dp[v]=1;
for(auto &z : g[v]){
dfs1(z);
dp[v]+=dp[z];
}
}
void dfs(int v,bool keep=0){
// for(int i=0;i<N;i++){
// dp[v][i]=(h[v]==i?0:c[v]);
// }
// cout<<"DFS "<<v<<' '<<h[v]<<endl;
int big=-1;
for(auto &z : g[v]){
if(big==-1 || dp[z]>dp[big])
big=z;
}
for(auto &z : g[v]){
if(z==big) continue;
dfs(z,0);
}
if(big!=-1){
dfs(big,1);
dps[v]=dps[big];
}
else{
dps[v]=new vec<pil>();
}
for(auto &z : g[v]){
if(z==big) continue;
for(auto &u : *dps[z]){
mp[u.f]+=u.s;
fen.upd(u.f,u.s);
}
(*dps[z]).clear();
}
if(h[v]!=0){
fen.upd(0,c[v]);mp[0]+=c[v];
mp[h[v]]-=c[v];fen.upd(h[v],-c[v]);
}else mp[h[v]]=0;
mp[h[v]+1]+=c[v];fen.upd(h[v]+1,c[v]);
auto it=mp.lower_bound(h[v]);
vec<pil> del;
ll myval=fen.get(h[v]);
while(it!=mp.begin()){
--it;
if(fen.get(it->f)>=myval)
del.pb(*it);
else break;
}
// for(auto &z : mp)
// cout<<"DP1 "<<v<<' '<<z.f<<' '<<fen.get(z.f)<<endl;
reverse(all(del));
for(auto &z : del){
ll dt=myval-fen.get(z.f);
fen.upd(z.f,dt);
// cout<<"CHECK "<<z.f<<' '<<fen.get(z.f)<<' '<<myval<<endl;
mp[z.f]+=dt;
// if(mp[z.f]==0)
// mp.erase(z.f);
}
{
ll dt=myval-fen.get(h[v]);
fen.upd(h[v],dt);
mp[h[v]]+=dt;
}
// for(auto &z : del)
// mp.erase(z.f),fen.upd(z.f,-z.s);
// for(auto &z : mp)
// cout<<"DP "<<v<<' '<<z.f<<' '<<fen.get(z.f)<<endl;
if(!keep){
for(auto &u : mp)
fen.upd(u.f,-u.s),(*dps[v]).pb(u);
mp.clear();
}
// f
}
signed main(){
fast_resp;
int n;
cin>>n;
vec<int>kek;
for(int i=0;i<n;i++){
cin>>a[i]>>h[i]>>c[i];--a[i];
if(a[i]!=i) g[a[i]].pb(i);
kek.pb(h[i]);
}
sort(all(kek));kek.erase(unique(all(kek)),kek.end());
for(int i=0;i<n;i++) h[i]=lower_bound(all(kek),h[i])-kek.begin();
dfs1(0);dfs(0);
cout<<(*dps[0])[0].s;
return 0;
}
/*
2
1 89 964898447
2 20 952129455
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
6612 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
6612 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
6612 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
