#include "tree.h"
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
  if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
  if(x > y) x = y;
}

inline int popcnt(int x){
  return __builtin_popcount(x);
}

inline int ctz(int x){
  return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
  ll ans = 1;
  while(k){
    if(k % 2 == 1) ans = ans * p % mod;
    p = p * p % mod;
    k /= 2; 
  }
  return ans;
}*/

int n,m;
int fa[200005],w[200005];
vector <int> son[200005];

void init(std::vector<int> _P, std::vector<int> _W) {
    n = SZ(_P);
    rep(u,2,n) fa[u] = _P[u - 1] + 1;
    rep(u,2,n) son[fa[u]].eb(u);
    rep(u,1,n){
        w[u] = _W[u - 1];
        chkmax(m,w[u]);
    }
}
int L,R;
int a[200005];
ll dp[2005][2],b[4005];
ll solve(int V){
    per(u,n,1){
        dp[u][0] = dp[u][1] = 0;
        for(int v:son[u]){
            dp[u][0] += max(dp[v][1] - R,dp[v][0]);
            dp[u][1] += max(dp[v][0] + L,dp[v][1]);
        }
        if(V < -w[u]) dp[u][0] = -linf;
        if(w[u] <= V) dp[u][1] = -linf;
    }
    if(0 > V) return max(dp[1][1],dp[1][0] + L);
    else return max(dp[1][0],dp[1][1] - R);
/*    a[0] = (0 > V);
    rep(u,1,n){
        if(V < -w[u]){
            a[u] = 1;
            continue;
        }else if(w[u] <= V){
            a[u] = 0;
            continue;
        }
        if(!son[u].empty()){
            a[u] = 1;
        }else{
            a[u] = 0;
        }
    }
    ll ret = 0;
    rep(u,1,n){
        if(!a[fa[u]] && a[u]) ret -= R;
        if(a[fa[u]] && !a[u]) ret += L;
    }
    cerr << "V=" << V << endl;
    rep(u,0,n) cerr << a[u] << " ";
    cerr << endl;
    cerr << ret << endl;
    return ret;*/
}

ll ssolve(int V){
    ll ret = solve(V);
//    cerr << V << "->" <<  ret << endl;
    return ret;
}

ll query(int _L,int _R) {
    L = _L;R = _R;
    ll answer = 0;
    rep(i,1,n){
        b[2 * i - 1] = -w[i];
        b[2 * i] = w[i];
    }
    b[2 * n + 1] = 0;
    sort(b + 1,b + 2 * n + 2);
    rep(i,1,2 * n) answer += 1ll * (b[i + 1] - b[i]) * ssolve(b[i]);
//    rep(V,-m,m - 1) ssolve(V);
    return answer;
}
/*
g++ grader.cpp tree5.cpp -o grader5.exe -Wall -Wshadow -O2 -std=c++14
*/