#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
int n;
vector<int>g[MAXN];
vector<int>g1[MAXN];
vector<int>g3[MAXN];
bool avoid[MAXN];
ll c[MAXN];
bool inroots[MAXN];
int a[MAXN],h[MAXN],subtree[MAXN];
void dfs11(int u,int p)
{
subtree[u]=1;
for(auto xd:g[u])
{
if(xd==p)continue;
dfs11(xd,u);
subtree[u]+=subtree[xd];
}
}
void dfs(int u,int p,map<int,ll> &mp)
{
int bc=-1,maxst=-1;
for(auto xd:g[u])
{
if(xd==p)continue;
if(subtree[xd]>maxst)
{
maxst=subtree[xd];
bc=xd;
}
}
if(bc==-1)
{
mp[0]=0;
mp[h[u]+1]=c[u];
return;
}
dfs(bc,u,mp);
for(auto xd:g[u])
{
if(xd==p||xd==bc)continue;
map<int,ll> tmp;
dfs(xd,u,tmp);
for(auto it:tmp)
{
if(it.second!=0)mp[it.first]+=it.second;
}
}
mp[h[u]+1]+=c[u];
mp[0]+=c[u];
mp[h[u]]-=c[u];
auto it=mp.lower_bound(h[u]);
int d=mp[h[u]];
auto it1=it;
it--;
while(d<0)
{
int t=(*it).first;
if((*it).second+d>=0)
{
mp[t]+=d;
d=0;
}
else
{
d+=(*it).second;
it1=it;
it--;mp.erase(it1);
}
}
mp[h[u]]=d;
}
bool used[MAXN];
vector<int>order;
int comp[MAXN];
void dfs1(int u)
{
used[u]=1;
for(auto xd:g[u])
{
if(used[xd]==0)dfs1(xd);
}
order.push_back(u);
}
void dfs2(int u,int c)
{
comp[u]=c;used[u]=1;
for(auto xd:g[u])
{
if(used[xd]==0)dfs2(xd,c);
}
}
vector<int>v;
void dfs3(int u)
{
used[u]=1;
v.push_back(u);
for(auto xd:g[u])if(!used[xd])dfs3(xd);
for(auto xd:g1[u])if(!used[xd])dfs3(xd);
}
int cnt[MAXN];
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i]>>h[i]>>c[i];
g[a[i]].push_back(i);
g1[i].push_back(a[i]);
}
for(int i=1;i<=n;i++)
{
if(used[i]==0)dfs1(i);
}
reverse(order.begin(),order.end());
memset(used,0,sizeof(used));
for(int i=0;i<order.size();++i)
{
if(used[order[i]]==0)dfs2(order[i],i);
}
memset(used,0,sizeof(used));
ll ans=0;
for(int i=1;i<=n;++i)
{
if(used[i]==0)
{
v.clear();
dfs3(i);
int y=-1;
for(int j=0;j<v.size();++j)
{
++cnt[comp[v[j]]];
if(cnt[comp[v[j]]]>1)y=comp[v[j]];
if(a[v[j]]==v[j])y=comp[v[j]];
}
for(int j=0;j<v.size();++j)
{
--cnt[comp[v[j]]];
}
if(y==-1)assert(false);
vector<pair<int,int> >roots;
for(int j=0;j<v.size();++j)
{
if(comp[v[j]]==y)
{
roots.push_back({h[v[j]],v[j]});
inroots[v[j]]=1;
}
}
sort(roots.rbegin(),roots.rend());
vector<int>g1;
for(auto xd:g[roots[roots.size()-1].second])
{
if(inroots[xd])continue;
else g1.push_back(xd);
}
g[roots.back().second]=g1;
for(int j=0;j<roots.size()-1;++j)
{
for(auto xd:g[roots[j].second])if(!inroots[xd])g[roots[roots.size()-1].second].push_back(xd);
g[roots[j].second]={roots[j+1].second};
}
/*cout<<roots.size()<<endl;
for(auto xd:roots)cout<<xd.second<<" ";
cout<<endl;
for(int j=1;j<=n;++j)
{
cout<<j<<":";
for(auto xd:g[j])cout<<" "<<xd;
cout<<endl;
}*/
dfs11(roots[0].second,0);
map<int,ll>mp;
dfs(roots[0].second,0,mp);
if(mp.count(0))ans+=mp[0];
}
}
cout<<ans<<endl;
return 0;
}
/*
3
2 3 4
3 2 5
1 3 2
*/
/*
4
2 3 5
3 4 6
1 2 7
2 5 4
*/
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:123:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i=0;i<order.size();++i)
| ~^~~~~~~~~~~~~
worst_reporter2.cpp:136:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int j=0;j<v.size();++j)
| ~^~~~~~~~~
worst_reporter2.cpp:142:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int j=0;j<v.size();++j)
| ~^~~~~~~~~
worst_reporter2.cpp:148:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(int j=0;j<v.size();++j)
| ~^~~~~~~~~
worst_reporter2.cpp:164:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for(int j=0;j<roots.size()-1;++j)
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14572 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14572 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
14572 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
16108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14572 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14572 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
14572 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
