#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
int n,parent[MAXN];
long long leaves[MAXN];
vector<int> v[MAXN];
long long cost[MAXN],ans,w[MAXN];
long long L,R,sum[MAXN],dp[MAXN];
pair<long long,long long> sol;
void dfs2(int x,long long times){
if(sum[x]==L)return;
times=min(times,sum[x]-L);
if(w[x]>0 and cost[x]>cost[sol.first]){
sol.first=x;
sol.second=min(times,w[x]);
}
for(int i:v[x]){
dfs2(i,times);
}
}
void dfs3(int x,long long times){
if(sum[x]==L)return;
times=min(times,sum[x]-L);
if(sol.first==0 or cost[x]<cost[sol.first]){
sol.first=x;
sol.second=times;
}
for(int i:v[x]){
dfs3(i,times);
}
}
void solve(int x){
sum[x]=w[x]=dp[x]=0;
if(v[x].empty()){
w[x]=sum[x]=L;
dp[x]=w[x]*cost[x];
return;
}
for(int i:v[x]){
solve(i);
sum[x]+=sum[i];
dp[x]+=dp[i];
}
if(sum[x]<=R)return;
while(true){
sol={0,0};
dfs2(x,sum[x]-R);
if(sol.first==0)break;
long long rem=min(sum[x]-R,sol.second);
int curr=sol.second;
w[curr]-=rem; sum[curr]-=rem;
dp[x]-=rem*cost[sol.first];
while(curr!=x){
curr=parent[curr];
sum[curr]-=rem;
}
if(sum[x]<=R)return;
}
while(true){
sol={0,0};
dfs3(x,sum[x]-R);
long long rem=min(sum[x]-R,sol.second);
int curr=sol.second;
w[curr]-=rem; sum[curr]-=rem;
dp[x]+=rem*cost[sol.first];
while(curr!=x){
assert(curr!=0);
curr=parent[curr];
sum[curr]-=rem;
}
if(sum[x]<=R)return;
}
}
void init(vector<int> P, vector<int> W){
n=int(P.size());
for(int i=1;i<=n;i++)cost[i]=W[i-1];
for(int i=1;i<P.size();i++){
v[P[i]+1].push_back(i+1);
parent[i+1]=P[i]+1;
}
}
long long query(int lt, int rt){
L=lt; R=rt;
solve(1);
return dp[1];
}
/*int main(){
init({-1, 0, 0}, {1, 1, 1});
cout<<query(1,1)<<"\n";
cout<<query(1,2)<<"\n";
return 0;
}*/
# | 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... |