#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];

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 cL,cR;
ll cof[200005][2];
void ssolve(int bas,int V){
    if(!bas) return;
    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;
        }
    }    
    rep(u,0,n){
        if(a[u] == -1) continue;
        
        for(int v:son[u]){
            if(a[v] != -1){
                if(a[u] && !a[v]) cL += bas;
                if(!a[u] && a[v]) cR -= bas;
            }else{
                c0 = c1 = cq = 0;
                dfs(v);
                if(!c1 && !a[u]){
                    cof[c0 + cq][0] += bas;
                }else{
                    cL += 1ll * bas * (c0 + cq);
                    cR -= 1ll * bas * (1 - a[u]);
                }
            }
        }
    }
}

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]);
    }
    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) ssolve(b[i + 1] - b[i],b[i]);
    rep(i,0,n){
        cof[i][1] = cof[i][0];
        cof[i][0] *= i;
    }
    per(i,n,1){
        cof[i - 1][0] += cof[i][0];
        cof[i - 1][1] += cof[i][1];
    }
}

ll query(int L,int R) {
    ll answer = cL * L + cR * R;
    int p = (R + L - 1) / L;
    chkmin(p,n + 1);
//    rep(i,p,n) answer += cof[i][0] * L - cof[]
    answer += cof[p][0] * L - cof[p][1] * R;
//    rep(i,0,n) max(0ll,1ll * i * L - R);
    return answer;
}
/*
g++ grader.cpp tree6.cpp -o grader6.exe -Wall -Wshadow -O2 -std=c++14
*/