#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
int n;
long long leaves[MAXN];
vector<int> v[MAXN];
long long cost[MAXN],ans;
long long L,R,sum[MAXN],dp[MAXN];
void dfs(int x){
if(v[x].empty())leaves[x]=1;
for(int i:v[x]){
dfs(i);
leaves[x]+=leaves[i];
}
}
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);
}
dfs(1);
sort(leaves+1,leaves+n+1);
}
long long query(int lt, int rt){
L=lt; R=rt;
long long ans=leaves[n]*L;
int l=1,r=n+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(leaves[tt]*L<=R){
l=tt;
}else{
r=tt;
}
}
long long big=n-l;
ans+=leaves[n]*L + (big-1)*R - big*R;
return ans;
/*ans=0;
solve(1);
return ans;*/
}
/*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... |