#include "bits/stdc++.h"
#include "tree.h"
using namespace std;
#define pb push_back
const int inf = 1e9 + 5;
struct SEGT{
vector<int> tree;
void init(int n){
tree.assign(4*n, 0);
}
void update(int ind, int l, int r, int pos, int val){
if(l == r){
tree[ind] += val;
}
else{
int m = (l + r)/2;
if(pos <= m) update(ind*2, l, m, pos, val);
else update(ind*2+1, m+1, r, pos, val);
tree[ind] = (tree[ind*2] + tree[ind*2+1]);
}
}
int query(int ind, int l, int r, int ql, int qr){
if(l > r || ql > qr || l > qr || r < ql) return 0;
if(l >= ql && r <= qr){
return tree[ind];
}
else{
int m = (l + r)/2;
return (query(ind*2, l, m, ql, qr) + query(ind*2+1, m+1, r, ql, qr));
}
}
};
SEGT seg;
int n;
vector<long long> p, w, act, ansarr, in, out;
vector<vector<int> > ch;
int leaf, tmr;
long long cur;
void dfs(int node, long long premn){
in[node] = ++tmr;
if(!ch[node].size()){
leaf++;
cur += w[node];
seg.update(1, 1, n, in[node], 1);
}
else if(node < premn){
act[node] = 1;
}
for(auto itr: ch[node]){
dfs(itr, min(premn, w[node]));
}
out[node] = tmr;
}
void init(vector<int> P, vector<int> W) {
n = (int)P.size();
p.resize(n);
w.resize(n);
act.assign(n, 0);
ansarr.assign(n+2, inf);
seg.init(n);
tmr = 0;
in.resize(n);
out.resize(n);
leaf = 0;
for(int i = 0; i < n; i++){
w[i] = W[i];
p[i] = P[i];
}
ch.resize(n);
for(int i = 1; i < n; i++){
ch[p[i]].pb(i);
}
dfs(0, inf);
ansarr[n] = cur;
set<array<long long, 3> > st;
for(int i = 0; i < n; i++){
if(act[i]){
int x = seg.query(1, 1, n, in[i], out[i]);
st.insert({w[i], x, i});
}
}
int root = leaf;
for(int i = n-1; i >= 1; i--){
if(leaf <= i){
ansarr[i] = cur;
continue;
}
while(true){
if(!st.size()){
cout<<"stupid"<<endl;
abort();
}
auto itr = *st.begin();
int x = seg.query(1, 1, n, in[i], out[i]);
if(!x){
st.erase(st.find(itr));
continue;
}
cur += itr[0];
seg.update(1, 1, n, in[itr[2]], -1);
array<long long, 3> nxt = itr;
nxt[1]--;
st.erase(st.find(itr));
if(nxt[1] >= 0) st.insert(nxt);
break;
}
ansarr[i] = cur;
}
}
long long query(int L, int R){
if(R >= n){
return ansarr[n];
}
else{
return ansarr[R];
}
}
