| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1089685 | 2024-09-16T21:52:05 Z | Lib | Fireworks (APIO16_fireworks) | C++14 | 0 ms | 0 KB |
#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.push(opt1+len[i]);
pq.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;
}