#include <bits/stdc++.h>
#include "tree.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n;
std::vector<int> p, w;
struct SegTree {
vector<int> tree;
void init() {
tree.assign(4*n, 0);
}
void query(int p, int l, int r, int i, int x) {
if (l>i || r<i) return;
if (l==r) {
tree[p] = x;
return;
}
int m = (l+r)/2;
query(2*p, l, m, i, x);
query(2*p+1, m+1, r, i, x);
int i1 = tree[2*p];
int i2 = tree[2*p+1];
if (i1==-1) {
tree[p] = i2;
return;
}
if (i2==-1) {
tree[p] = i1;
return;
}
if (w[i1] < w[i2]) tree[p] = i1;
else tree[p] = i2;
}
int rmq(int p, int l, int r, int i, int j) {
if (l > j || r < i) return -1;
if (i <= l && r <= j) {
return tree[p];
}
int m = (l+r)/2;
int i1 = rmq(2*p, l, m, i, j);
int i2 = rmq(2*p+1, m+1, r, i, j);
if (i1==-1) return i2;
if (i2==-1) return i1;
if (w[i1] < w[i2]) return i1;
else return i2;
}
};
SegTree st;
vector<vector<int>> adj;
vector<int> leaf;
vector<int> in, out;
vector<bool> isleaf;
int t;
void dfs(int u, int p=-1) {
bool can = true;
in[u] = t++;
for (auto x : adj[u]) {
if (x==p) continue;
dfs(x, u);
can = false;
}
out[u] = t;
if (can) {
leaf.push_back(u);
isleaf[u] = true;
}
}
void init(std::vector<int> P, std::vector<int> W) {
p = P;
w = W;
n = (int)p.size();
adj.assign(n, {});
in.assign(n, 0);
out.assign(n, 0);
isleaf.assign(n, false);
t=0;
for (int i=1; i<n; i++) {
int a = i;
int b = p[i];
adj[a].push_back(b);
adj[b].push_back(a);
}
t=0;
dfs(0);
}
long long query(int L, int R) {
vector<ll> c(n, 0);
vector<ll> S(n, 0);
st.init();
for (int i=0; i<n; i++) {
if (!isleaf[i]) st.query(1, 0, n-1, in[i], i);
else st.query(1, 0, n-1, in[i], -1);
}
for (int i=n-1; i>=0; i--) {
if (isleaf[i]) {
c[i] = L;
S[i] = L;
}
else {
while (S[i] > R) {
int idx = st.rmq(1, 0, n-1, in[i], out[i]-1);
S[idx]--;
S[i]--;
c[idx]--;
if (S[idx] == L) st.query(1, 0, n-1, in[idx], -1);
}
if (S[i] == L) st.query(1, 0, n-1, in[i], -1);
}
if (i==0) continue;
S[p[i]] += S[i];
}
ll ans=0;
for (int i=0; i<n; i++) {
ans += abs(c[i])*w[i];
}
return ans;
}
