//Trumling ©
//Αφόδευε υψηλά και ηγνάντει
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#include "tree.h"
int n;
vector<ll> w;
vector<ll>f;
vector<vector<ll>>g;
vector<priority_queue<pair<ll,ll>>>v;
ll ans=0;
void dfs(int start,int pre,int L,int R)
{
for(auto x:g[start])
if(x!=pre)
{
dfs(x,start,L,R);
f[start]+=f[x];
while(!v[x].empty())
{
if(f[v[x].top().S]>L)
v[start].push(v[x].top());
v[x].pop();
}
}
v[start].push({-w[start],start});
if(f[start]==0)
{
f[start]=L;
ans+=w[start]*L;
}
while(f[start]>R)
{
ll can=f[v[start].top().S]-L;
ll must=f[start]-R;
if(can>must)
{
if(v[start].top().S!=start)
f[v[start].top().S]-=must;
f[start]-=must;
ans+=must*(-v[start].top().F);
}
else
{
if(v[start].top().S!=start)
f[v[start].top().S]-=can;
f[start]-=can;
ans+=can*(-v[start].top().F);
v[start].pop();
}
}
ll used=0,sum=f[start];
priority_queue<pair<ll,ll>>pq;
while(!v[start].empty() && used < sum - L)
{
ll can = min(sum - L - used , f[v[start].top().S] - L);
f[v[start].top().S]= L + can;
pq.push(v[start].top());
v[start].pop();
used+=can;
}
v[start]=pq;
}
void init(std::vector<int> p, std::vector<int> W) {
for(auto x:W)
w.pb(x);
n = (int)p.size();
g.assign(n,vector<ll>());
for(int i=1;i<n;i++)
{
// cout<<i<<' '<<p[i]<<',';
g[i].pb(p[i]);
g[p[i]].pb(i);
}
}
long long query(int L, int R)
{
ans=0;
f.assign(n,0);
v.assign(n,priority_queue<pair<ll,ll>>());
dfs(0,0,L,R);
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |