#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
vector<int>adj[maxn];
pair<int,int>par[maxn];
int n;
long long sum=0;
void vorod(){
int d;
cin>>n>>d;
n+=d;
for(int 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<int>pq[maxn];
int val[maxn];
void add(int u,int x,int z){
//cout<<"wtf: "<<u<<" "<<x<<endl;
int nx=pq[u].top();
pq[u].pop();
int 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(int u,int v){
int fu=u;
if(pq[u].size()<pq[v].size()){
swap(u,v);
}
int 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(int u,int 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((int)adj[u].size()==0){
pq[u].push(len);
pq[u].push(len);
}
//cout<<"khor: "<<u<<endl;
priority_queue<int>qp=pq[u];
while(qp.size()>0){
//cout<<qp.top()+val[u]<<" ";
qp.pop();
}
//cout<<"\n";
if(u!=1){
int f=pq[u].top();
pq[u].pop();
int 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((int)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;
int sz=all.size();
for(int 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(int, int, int)':
fireworks.cpp:25:6: warning: unused variable 'ps' [-Wunused-variable]
25 | int ps=pq[u].top();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
20056 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
20060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
20056 KB |
Output is correct |
| 2 |
Correct |
4 ms |
20256 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
20060 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
20056 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
20060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
20056 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
20060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
