#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
vector<pl>adj[300010];
priority_queue<pl,vector<pl>,less<pl> >pq1[300010];
priority_queue<pl,vector<pl>,greater<pl> >pq2[300010];
int pct;
int pn[300010];
ll b[300010];
ll ans;
inline void pqe(priority_queue<pl,vector<pl>,less<pl> >&pq,ll t)
{
pl x(t,1);
if(pq.top().fi==x.fi)
x.se+=pq.top().se,pq.pop(),pq.ep(x);
else
pq.ep(x);
return;
}
inline void pqe(priority_queue<pl,vector<pl>,greater<pl> >&pq,ll t)
{
pl x(t,1);
if(pq.top().fi==x.fi)
x.se+=pq.top().se,pq.pop(),pq.ep(x);
else
pq.ep(x);
return;
}
inline void pqe(priority_queue<pl,vector<pl>,less<pl> >&pq,pl x)
{
if(pq.top().fi==x.fi)
x.se+=pq.top().se,pq.pop(),pq.ep(x);
else
pq.ep(x);
return;
}
inline void pqe(priority_queue<pl,vector<pl>,greater<pl> >&pq,pl x)
{
if(pq.top().fi==x.fi)
x.se+=pq.top().se,pq.pop(),pq.ep(x);
else
pq.ep(x);
return;
}
inline void in1(int n,ll x)
{
if(x>pq2[n].top().fi+b[n])
{
ans+=x-(pq2[n].top().fi+b[n]);
pqe(pq2[n],x-b[n]);
pl t=pq2[n].top();
pqe(pq1[n],pq2[n].top().fi);
pq2[n].pop();
t.se--;
if(t.se>0)
pq2[n].ep(t);
}
else
pqe(pq1[n],x-b[n]);
return;
}
inline void in2(int n,ll x)
{
if(x<pq1[n].top().fi+b[n])
{
ans+=(pq2[n].top().fi+b[n])-x;
pqe(pq1[n],x-b[n]);
pl t=pq1[n].top();
pqe(pq2[n],pq1[n].top().fi);
pq1[n].pop();
t.se--;
if(t.se>0)
pq1[n].ep(t);
}
else
pqe(pq2[n],x-b[n]);
return;
}
inline void in1(int n,pl t)
{
ll x=t.fi;
if(x>pq2[n].top().fi+b[n])
{
ans+=(x-(pq2[n].top().fi+b[n]))*t.se;
pqe(pq2[n],pl(x-b[n],t.se));
pl tt=pq2[n].top();
pqe(pq1[n],tt.fi);
pq2[n].pop();
tt.se--;
if(tt.se>0)
pq2[n].ep(tt);
}
else
pqe(pq1[n],pl(x-b[n],t.se));
return;
}
inline void in2(int n,pl t)
{
ll x=t.fi;
if(x<pq1[n].top().fi+b[n])
{
ans+=((pq2[n].top().fi+b[n])-x)*t.se;
pqe(pq1[n],pl(x-b[n],t.se));
pl tt=pq1[n].top();
pqe(pq2[n],tt.fi);
pq1[n].pop();
tt.se--;
if(tt.se>0)
pq1[n].ep(tt);
}
else
pqe(pq2[n],pl(x-b[n],t.se));
return;
}
void dfs(int x)
{
if(adj[x].empty())
{
pn[x]=pct++;
pq1[pn[x]].ep(0,1);
pq2[pn[x]].ep(0,1);
return;
}
int sz=-1;
for(pl&t:adj[x])
{
dfs(t.fi);
b[pn[t.fi]]+=t.se;
ll l=pq1[pn[t.fi]].top().fi;
ll ct=0;
while(!pq1[pn[t.fi]].empty()&&pq1[pn[t.fi]].top().fi>=l-t.se)
ct+=pq1[pn[t.fi]].top().se,pq1[pn[t.fi]].pop();
if(ct>1)
pq1[pn[t.fi]].ep(l-t.se,ct-1);
pq1[pn[t.fi]].ep(l,1);
l=pq2[pn[t.fi]].top().fi;
while(!pq2[pn[t.fi]].empty())
pq2[pn[t.fi]].pop();
pq2[pn[t.fi]].ep(l,1);
if(sz<(int)pq1[pn[t.fi]].size())
sz=pq1[pn[x]=pn[t.fi]].size();
}
for(pl&t:adj[x])
{
if(pn[x]==pn[t.fi])
continue;
while(!pq1[pn[t.fi]].empty())
{
pl tt=pq1[pn[t.fi]].top();
tt.fi+=b[pn[t.fi]];
in1(pn[x],tt);
pq1[pn[t.fi]].pop();
}
while(!pq2[pn[t.fi]].empty())
{
pl tt=pq2[pn[t.fi]].top();
tt.fi+=b[pn[t.fi]];
in2(pn[x],tt);
pq2[pn[t.fi]].pop();
}
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int v,c,p;
cin>>v>>c;
v+=c;
for(int i=1;i++<v;)
cin>>p>>c,adj[p].eb(i,c);
dfs(1);
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
26104 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
26232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
26232 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
26232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
26104 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
26232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
26104 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
26232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
