#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
#define pb push_back
const int N = 2000 + 4;
const int INF = 1ll << 20;
int n;
vector<int> p, w;
vector<int> adj[N];
void init(std::vector<int> P, std::vector<int> W) {
n = P.size();
p = P;
w = W;
for (int i=1; i<n; i++) adj[p[i]].pb(i);
}
int dp[N][N];
void dfs(int v, int l, int r) {
for (int x=0; x<N; x++) dp[v][x]= INF;
if (adj[v].empty()) {
for (int x=l; x<=r; x++) dp[v][x] = w[v] * x;
return;
}
dp[v][0] = 0;
for (int u : adj[v]) {
dfs(u, l, r);
vector<int> old_dp;
for (int x=0; x<N; x++) old_dp.pb(dp[v][x]);
for (int x=0; x<N; x++) dp[v][x]= INF;
for (int x=0; x<N; x++) for (int y=0; y<N; y++) for (int z=l; z<=r; z++) {
chmin(dp[v][x], old_dp[y] + dp[u][z] + abs(y+z - x) * w[v]);
}
}
}
long long query(int L, int R) {
dfs(0, L, R);
return *min_element(dp[0]+L, dp[0]+R+1);
}
