#include <bits/stdc++.h>
using namespace std;
priority_queue <long long> pq[300003];
long long par[300003];
long long children[300003];
long long len[300003];
long long dp[300003];
int main(){
int n,m;
cin>>n>>m;
for(int i=2;i<=n;i++){
cin>>par[i]>>len[i];
children[i]++;
//this is a leaf
if(i>n){
dp[par[i]]-=len[i];
//Similar to other slope trick things. One push for the action of "shrinking the edge to 0", one push for the action of undoing the other one
pq[par[i]].push(len[i]);
pq[par[i]].push(len[i]);
}
}
//Merging answers from children to parent, pushing sub-pqs into top-pqs
for(int i=n;i>=2;i--){
for(int k=1;k<=children[i];k++){
//undo-ing the undo operations
dp[i]+=pq[i].top();
pq[i].pop();
long long opt1,opt2;
//2 most optimal undo operations
opt1=pq[i].top();
pq[i].pop();
opt2=pq[i].top();
pq[i].pop();
pq[i].push(opt1+len[i]);
pq[i].push(opt2+len[i]);
dp[i]-=len[i];//pre-paid
long long tmp;
dp[par[i]]+=dp[i];//pushing the answer to root
//classic small-to-large merging here
if(pq[par[i]].size()<pq[i].size()){
swap(pq[par[i]],pq[i]);
}
while(!pq[i].empty()){
tmp=pq[i].top();
pq[i].pop();
pq[par[i]].push(tmp);
}
}
}
long long ans=dp[1];
//final undo ops
for(int i=1;i<=children[1];i++){
dp[1]+=pq[1].top();
pq[1].pop();
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
21596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
