#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
ll n;
vector<ll>g[MAXN];
ll a[MAXN],h[MAXN],c[MAXN],subtree[MAXN];
void dfs1(ll u,ll p)
{
subtree[u]=1;
for(auto xd:g[u])
{
if(xd==p)continue;
dfs1(xd,u);
subtree[u]+=subtree[xd];
}
}
void dfs(ll u,ll p,map<int,ll> &mp)
{
ll 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[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)
{
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]);
while(mp[h[u]]<0)
{
it--;
ll t=(*it).first;
if(mp[t]+mp[h[u]]>=0)
{
mp[t]+=mp[h[u]];
mp[h[u]]=0;
}
else
{
mp[h[u]]+=mp[t];
mp[t]=0;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(ll i=1;i<=n;++i)
{
cin>>a[i]>>h[i]>>c[i];
if(i!=1)g[a[i]].push_back(i);
}
dfs1(1,0);
map<int,ll>mp;
dfs(1,0,mp);
cout<<mp[0]<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
12 ms |
5868 KB |
Output is correct |
6 |
Correct |
9 ms |
5356 KB |
Output is correct |
7 |
Correct |
8 ms |
5356 KB |
Output is correct |
8 |
Correct |
14 ms |
5884 KB |
Output is correct |
9 |
Correct |
12 ms |
5356 KB |
Output is correct |
10 |
Correct |
9 ms |
5484 KB |
Output is correct |
11 |
Correct |
7 ms |
5356 KB |
Output is correct |
12 |
Correct |
135 ms |
7020 KB |
Output is correct |
13 |
Correct |
8 ms |
6380 KB |
Output is correct |
14 |
Correct |
96 ms |
6764 KB |
Output is correct |
15 |
Correct |
15 ms |
5868 KB |
Output is correct |
16 |
Correct |
14 ms |
5996 KB |
Output is correct |
17 |
Correct |
10 ms |
5356 KB |
Output is correct |
18 |
Correct |
7 ms |
5356 KB |
Output is correct |
19 |
Correct |
14 ms |
6272 KB |
Output is correct |
20 |
Correct |
8 ms |
5868 KB |
Output is correct |
21 |
Correct |
8 ms |
5868 KB |
Output is correct |
22 |
Correct |
8 ms |
5612 KB |
Output is correct |
23 |
Correct |
6 ms |
5356 KB |
Output is correct |
24 |
Correct |
13 ms |
6252 KB |
Output is correct |
25 |
Correct |
8 ms |
5868 KB |
Output is correct |
26 |
Correct |
11 ms |
7020 KB |
Output is correct |
27 |
Correct |
168 ms |
6124 KB |
Output is correct |
28 |
Correct |
311 ms |
6528 KB |
Output is correct |
29 |
Correct |
287 ms |
6764 KB |
Output is correct |
30 |
Correct |
14 ms |
6764 KB |
Output is correct |
31 |
Correct |
14 ms |
6764 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
5740 KB |
Output is correct |
2 |
Correct |
567 ms |
39120 KB |
Output is correct |
3 |
Correct |
352 ms |
15852 KB |
Output is correct |
4 |
Correct |
552 ms |
34924 KB |
Output is correct |
5 |
Correct |
357 ms |
15568 KB |
Output is correct |
6 |
Correct |
250 ms |
15212 KB |
Output is correct |
7 |
Correct |
181 ms |
15084 KB |
Output is correct |
8 |
Execution timed out |
2090 ms |
62340 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
12 ms |
5868 KB |
Output is correct |
6 |
Correct |
9 ms |
5356 KB |
Output is correct |
7 |
Correct |
8 ms |
5356 KB |
Output is correct |
8 |
Correct |
14 ms |
5884 KB |
Output is correct |
9 |
Correct |
12 ms |
5356 KB |
Output is correct |
10 |
Correct |
9 ms |
5484 KB |
Output is correct |
11 |
Correct |
7 ms |
5356 KB |
Output is correct |
12 |
Correct |
135 ms |
7020 KB |
Output is correct |
13 |
Correct |
8 ms |
6380 KB |
Output is correct |
14 |
Correct |
96 ms |
6764 KB |
Output is correct |
15 |
Correct |
15 ms |
5868 KB |
Output is correct |
16 |
Correct |
14 ms |
5996 KB |
Output is correct |
17 |
Correct |
10 ms |
5356 KB |
Output is correct |
18 |
Correct |
7 ms |
5356 KB |
Output is correct |
19 |
Correct |
14 ms |
6272 KB |
Output is correct |
20 |
Correct |
8 ms |
5868 KB |
Output is correct |
21 |
Correct |
8 ms |
5868 KB |
Output is correct |
22 |
Correct |
8 ms |
5612 KB |
Output is correct |
23 |
Correct |
6 ms |
5356 KB |
Output is correct |
24 |
Correct |
13 ms |
6252 KB |
Output is correct |
25 |
Correct |
8 ms |
5868 KB |
Output is correct |
26 |
Correct |
11 ms |
7020 KB |
Output is correct |
27 |
Correct |
168 ms |
6124 KB |
Output is correct |
28 |
Correct |
311 ms |
6528 KB |
Output is correct |
29 |
Correct |
287 ms |
6764 KB |
Output is correct |
30 |
Correct |
14 ms |
6764 KB |
Output is correct |
31 |
Correct |
14 ms |
6764 KB |
Output is correct |
32 |
Correct |
12 ms |
5740 KB |
Output is correct |
33 |
Correct |
567 ms |
39120 KB |
Output is correct |
34 |
Correct |
352 ms |
15852 KB |
Output is correct |
35 |
Correct |
552 ms |
34924 KB |
Output is correct |
36 |
Correct |
357 ms |
15568 KB |
Output is correct |
37 |
Correct |
250 ms |
15212 KB |
Output is correct |
38 |
Correct |
181 ms |
15084 KB |
Output is correct |
39 |
Execution timed out |
2090 ms |
62340 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |