#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);
    son[0].eb(1);
    rep(u,1,n){
        w[u] = _W[u - 1];
        chkmax(m,w[u]);
    }
}
int L,R;
int a[200005],b[200005],c0,c1,cq;
void dfs(int u){
    int ssum = 0;
    if(a[u] == -1){
        for(int v:son[u]) dfs(v);
        ssum += SZ(son[u]);
    } 
    if(!ssum){
        if(a[u] == -1) cq++;
        else if(!a[u]) c0++;
        else c1++;
    }
}

ll ssolve(int V){
    a[0] = (0 > V);
    rep(u,1,n){
        if(V < -w[u]){
            a[u] = 1;
        }else if(w[u] <= V){
            a[u] = 0;
        }else{
            a[u] = -1;
        }
    }    
    ll answer = 0;
    rep(u,0,n){
        if(a[u] == -1) continue;
        
        for(int v:son[u]){
            if(a[v] != -1){
                if(a[u] && !a[v]) answer += L;
                if(!a[u] && a[v]) answer -= R;
            }else{
                c0 = c1 = cq = 0;
                dfs(v);
                if(!c1 && !a[u]) answer += max(0ll,1ll * (c0 + cq) * L - R);
                else answer += 1ll * (c0 + cq) * L - R * (1 - a[u]);
            }
        }
    }
/*    rep(u,0,n) cerr << a[u] << " ";
    cerr << endl;
    cerr << "V=" << V << " " << answer << endl;*/
    return answer;
}

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 tree6.cpp -o grader6.exe -Wall -Wshadow -O2 -std=c++14
*/