#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+10;
vector<long long>adj[maxn];
pair<long long,long long>par[maxn];
long long n;
long long sum=0;
void vorod(){
long long d;
cin>>n>>d;
n+=d;
for(long long i=2;i<=n;i++){
cin>>par[i].first>>par[i].second;
adj[par[i].first].push_back(i);
sum+=par[i].second;
}
}
priority_queue<long long>pq[maxn];
long long val[maxn];
void add(long long u,long long x,long long z){
//cout<<"wtf: "<<u<<" "<<x<<endl;
long long nx=pq[u].top();
pq[u].pop();
long long ps=pq[u].top();
pq[u].push(nx);
if(z==0){
if(x<=nx){
pq[u].pop();
pq[u].push(x);
return ;
}
return ;
}
pq[u].push(x);
}
void merge(long long u,long long v){
long long fu=u;
if(pq[u].size()<pq[v].size()){
swap(u,v);
}
long long z=0;
while(pq[v].size()>0){
auto x=pq[v].top();
pq[v].pop();
//cout<<u<<" "<<v<<" "<<val[u]<<" "<<val[v]<<" "<<x<<" tof"<<endl;
x+=val[v];
x-=val[u];
if(z<2){
add(u,x,z);
z++;
}
else{
pq[u].push(x);
}
}
if(u!=fu){
swap(pq[u],pq[fu]);
swap(val[u],val[fu]);
}
}
void solve(long long u,long long len=0){
if(u!=1){
len+=par[u].second;
}
//cout<<"injy: "<<u<<" "<<len<<endl;
for(auto x:adj[u]){
solve(x,len);
merge(u,x);
}
//cout<<"tamam: "<<u<<endl;
if((long long)adj[u].size()==0){
pq[u].push(len);
pq[u].push(len);
}
//cout<<"khor: "<<u<<endl;
// priority_queue<long long>qp=pq[u];
// while(qp.size()>0){
//cout<<qp.top()+val[u]<<" ";
// qp.pop();
// }
//cout<<"\n";
if(u!=1){
long long f=pq[u].top();
pq[u].pop();
long long ff=pq[u].top();
pq[u].pop();
val[u]-=par[u].second;
pq[u].push(ff+par[u].second);
pq[u].push(f+par[u].second);
}
//cout<<"khor: "<<u<<endl;
// qp=pq[u];
// while(qp.size()>0){
//cout<<qp.top()+val[u]<<" ";
// qp.pop();
// }
//cout<<"\n";
return ;
}
void khor(){
//cout<<"suma: "<<sum<<" "<<val[1]<<endl;
vector<long long>all;
while((long long)pq[1].size()>0){
all.push_back(pq[1].top()+val[1]);
//cout<<pq[1].top()+val[1]<<endl;
pq[1].pop();
}
all.push_back(0);
long long res=sum;
long long sz=all.size();
for(long long i=0;i<sz-1;i++){
// //cout<<"tof: "<<all[i]<<" "<<i<<" "<<(all[i]-all[i+1])*i<<endl;
res-=(all[i]-all[i+1])*(i);
}
cout<<res<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vorod();
solve(1);
khor();
}
Compilation message
fireworks.cpp: In function 'void add(long long int, long long int, long long int)':
fireworks.cpp:25:12: warning: unused variable 'ps' [-Wunused-variable]
25 | long long ps=pq[u].top();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
19548 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
19644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
19548 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
19548 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
