#include <bits/stdc++.h>
#include "tree.h"
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define each(a, x) for (auto &a : x)
#define FOR(i, a, b) for (int i = a; i < b; i++)
int n, l, r;
vi par, weight;
vvi adj;
int dfs(int u, int p, int &total_cost) {
if (sz(adj[u]) == 1) {
total_cost += l * weight[u];
return l;
}
int child_sum = 0;
each(v, adj[u]) {
if (v == p) continue;
child_sum += dfs(v, u, total_cost);
}
int my_sum = 0;
if (par[u] == -1 || weight[par[u]] <= weight[u]) {
my_sum = r - child_sum;
} else {
my_sum = l - child_sum;
}
total_cost += abs(my_sum) * weight[u];
return child_sum + my_sum;
}
void init(vi P, vi W) {
par = P; weight = W;
n = sz(par);
adj.assign(n, vi());
FOR(i, 1, n) {
adj[i].pb(par[i]);
adj[par[i]].pb(i);
}
}
ll query(int L, int R) {
l = L; r = R;
int total_cost = 0; dfs(0, -1, total_cost);
return total_cost;
}
