//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())
{
v[start].push(v[x].top());
v[x].pop();
}
}
if(f[start]==0)
{
f[start]=L;
ans+=w[start]*L;
}
while(f[start]>R && !v[start].empty() && -v[start].top().F < w[start])
{
pair<ll,ll>curr=v[start].top();
v[start].pop();
ll can=curr.S;
ll must=f[start]-R;
if(can>must)
{
curr.S-=must;
f[start]-=must;
ans+=must*(-curr.F);
v[start].push(curr);
}
else
{
curr.S-=can;
f[start]-=can;
ans+=can*(-curr.F);
}
}
if(f[start]>R)
{
ans+=(f[start]-R)*w[start];
f[start]=R;
}
v[start].push({-w[start],f[start] - L});
ll used=0;
priority_queue<pair<ll,ll>>pq;
while(!v[start].empty() && used < (f[start] - L))
{
pair<ll,ll>curr=v[start].top();
v[start].pop();
ll can = min(f[start] - L - used , curr.S);
curr.S = can;
pq.push(curr);
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... |