#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
#define each(a,b) for (auto &a : b)
const int MAXN = 1<<18;
int j[18][MAXN], jm[18][MAXN];
ll w[MAXN];
ll ans[MAXN], csum[MAXN], a0;
vi k[MAXN], legs[MAXN];
void dfs(int i, int p) {
a0 += w[i]*(csum[i] = abs(1-sz(k[i])));
if (sz(k[i]) == 0) return;
j[0][i] = p;
jm[0][i] = min(w[i], w[p]);
for (int b = 1; b < 18; b++) {
j[b][i] = j[b-1][j[b-1][i]];
jm[b][i] = min(jm[b-1][i], jm[b-1][j[b-1][i]]);
}
for (int j : k[i]) dfs(j, i);
if (w[i]) {
int cur = i;
for (int b = 17; b >= 0; b--) {
if (jm[b][cur] >= w[i]) cur = j[b][cur];
}
legs[cur].push_back(i);
csum[j[0][cur]] += csum[i];
}
sort(legs[i].begin(), legs[i].end(), [&](int a, int b){
return w[a] > w[b];
});
int last = 0;
for (int j : legs[i]) {
ans[last+1] -= w[j]-w[p];
ans[last+1+csum[j]] += w[j]-w[p];
last = last+csum[j];
}
}
void init(std::vector<int> P, std::vector<int> W) {
for (int i = 0; i < P.size(); i++) {
k[P[i]+1].push_back(i+1);
w[i+1]=W[i];
}
dfs(1, 0);
for (int i = 1; i < MAXN; i++) ans[i] += ans[i-1];
ans[0] += a0;
for (int i = 1; i < MAXN; i++) ans[i] += ans[i-1];
}
long long query(int L, int R) {
if (L != 1) {
int Q = R/L, S = R%L;
return (L-S)*query(1, Q) + S*query(1, Q+1);
}
return ans[min(R-1, MAXN-1)];
}
// int main() {
// init(vi{-1,0,0}, vi{1,1,1});
// cout << query(1,1);
// cout << query(1,2);
// }
