#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3uHasSr ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
const int inf=1e18;
signed main(){
_3uHasSr;
int n;
cin>>n;
vec(pii) a(n);
vi g(n);
vec(vi) rg(n);
rep(i,n){
int u,h,c;
cin>>u>>h>>c;
u-=1;
g[i]=u;
rg[u].pb(i);
a[i]={h,c};
}
vec(std::map<int,int>) dp(n);
vi center(n);
rep(v,n){
center[v]=v;
}
per(v,n){
if(!v) break;
auto [h,c]=a[v];
dp[center[v]][h]+=c;
auto it=dp[center[v]].find(h);
if(it!=dp[center[v]].begin()){
it=prev(it);
while(1){
auto nit=it;
bool lok=0;
if(it==dp[center[v]].begin()){
lok=1;
}else{
it=prev(it);
}
pii _p=*nit;
if(c>=_p.se){
c-=_p.se;
dp[center[v]].erase(nit);
}else{
_p.se-=c;
dp[center[v]].erase(nit);
dp[center[v]][_p.fi]+=_p.se;
break;
}
if(lok){
break;
}
}
}
int up=g[v];
int u0=center[up],u1=center[v];
if(sz(dp[u0])<sz(dp[u1])){
swap(u0,u1);
center[up]=center[v];
}
for(auto p:dp[u1]){
dp[u0][p.fi]+=p.se;
}
}
int res=0;
rep(v,n){
res+=a[v].se;
}
for(auto p:dp[center[0]]){
// print(p.fi,p.se);
res-=p.se;
}
print(res);
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
