#include "tree.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<map>
#include<vector>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
namespace{
int n;
vector<vector<int>> graph;
vector<ll> vec, dp;
ll l, r;
ll dfs(int node, int parent){
ll ans = 0;
for(auto &x: graph[node]){
if(x == parent) continue;
ans += dfs(x, node);
dp[node] += dp[x];
}
if(dp[node] < l){
assert((int)graph[node].size() == 1);
ans += vec[node] * (l - dp[node]);
dp[node] = l;
}
else if(dp[node] > r){
ans += vec[node] * (dp[node] - r);
dp[node] = r;
}
return ans;
}
}
void init(std::vector<int> P, std::vector<int> W) {
n = (int)P.size();
graph.resize(n + 1);
vec.resize(n + 1);
dp.resize(n + 1);
for(int i = 1; i < n; i++){
graph[i + 1].push_back(P[i] + 1);
graph[P[i] + 1].push_back(i + 1);
}
for(int i = 1; i <= n; i++) vec[i] = W[i - 1];
}
long long query(int L, int R) {
l = L;
r = R;
fill(dp.begin(), dp.end(), 0);
return dfs(1, 0);
}
