#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;
}*/
bool _st;

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

ll cL,cR;
ll cof[200005][2];
int cnt;
#define uc unsigned char
int top;
int stk[60000005];
struct node{
    int l,r,c0,cq,t0,tq;
    uc c1,t1,cs,ts;
}tree[60000005];
#define ls(rt) tree[rt].l
#define rs(rt) tree[rt].r 
void Q(int &u){
    if(u) return;
    u = stk[top--];
    tree[u] = node();
    assert(top);
}

void S(int u){
    ls(u) = rs(u) = 0;
    tree[u].t0 = tree[u].t1 = tree[u].tq = tree[u].ts = 0;
}

void clone(int rt){
    if(!ls(rt)) Q(ls(rt));
    if(!rs(rt)) Q(rs(rt));
}

const uc one = 1,two = 2;
void upd(int rt,int t0,uc t1,int tq,uc ts){
    tree[rt].c0 += t0;tree[rt].t0 += t0;
    tree[rt].c1 += t1;tree[rt].t1 |= t1;
    tree[rt].cq += tq;tree[rt].tq += tq;
    tree[rt].cs += ts;tree[rt].ts += ts;  
    chkmin(tree[rt].c1,one);
    chkmin(tree[rt].cs,two);  
    chkmin(tree[rt].t1,one);
    chkmin(tree[rt].ts,two);  
}

void pushdown(int rt){
    clone(rt);
    upd(ls(rt),tree[rt].t0,tree[rt].t1,tree[rt].tq,tree[rt].ts);
    upd(rs(rt),tree[rt].t0,tree[rt].t1,tree[rt].tq,tree[rt].ts);
    tree[rt].t0 = tree[rt].t1 = tree[rt].tq = tree[rt].ts = 0;
}

void clr(int &rt,int l,int r,int C){
    if(!ls(rt) && !rs(rt)){
//        printf("range [%d,%d] C=%d c0=%d c1=%d cq=%d cs=%d\n",l,r,C,tree[rt].c0,tree[rt].c1,tree[rt].cq,tree[rt].cs);
        if(tree[rt].cs == 1 && !tree[rt].cq){
            if(C && tree[rt].c0) cL += r - l + 1;
            if(!C && tree[rt].c1) cR -= r - l + 1;                
        }else if(!tree[rt].c1 && !C){
            cof[tree[rt].c0 + tree[rt].cq][0] += r - l + 1;
        }else{
            cL += 1ll * (r - l + 1) * (tree[rt].c0 + tree[rt].cq);
            cR -= 1ll * (r - l + 1) * (1 - C);                
        }     
        stk[++top] = rt;
        rt = 0;  
        return;        
    }
    int mid = (l + r) >> 1;
//    printf("[%d,%d] ts=%d cs=%d\n",l,r,tree[rt].ts,tree[rt].cs);
    pushdown(rt);
    clr(ls(rt),l,mid,C);
    clr(rs(rt),mid+1,r,C);
    stk[++top] = rt;
    rt = 0;
}

void clr(int &rt,int l,int r,int L,int R,int C){
    if(l == L && r == R){
        clr(rt,l,r,C);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt);
    if(R <= mid){
        clr(ls(rt),l,mid,L,R,C);
    }else if(L > mid){
        clr(rs(rt),mid+1,r,L,R,C);
    }else{
        clr(ls(rt),l,mid,L,mid,C);
        clr(rs(rt),mid+1,r,mid+1,R,C);
    }
}

void upload(int rt,int l,int r,int L,int R,int t0,uc t1,int tq){
    if(l == L && r == R){
        upd(rt,t0,t1,tq,1);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt);
    if(R <= mid){
        upload(ls(rt),l,mid,L,R,t0,t1,tq);
    }else if(L > mid){
        upload(rs(rt),mid+1,r,L,R,t0,t1,tq);        
    }else{
        upload(ls(rt),l,mid,L,mid,t0,t1,tq);  
        upload(rs(rt),mid+1,r,mid+1,R,t0,t1,tq);        
    }
}

int Merge(int x,int y){
    if(!x || !y) return x + y;
    if(!ls(x) && !rs(x)){
        upd(y,tree[x].c0,tree[x].c1,tree[x].cq,tree[x].cs);
        stk[++top] = x;
        return y;
    }
    if(!ls(y) && !rs(y)){
        upd(x,tree[y].c0,tree[y].c1,tree[y].cq,tree[y].cs);
        stk[++top] = y;
        return x;        
    }
    pushdown(x);pushdown(y);
    ls(x) = Merge(ls(x),ls(y));
    rs(x) = Merge(rs(x),rs(y));
    stk[++top] = y;
    return x;
}

void prt(int rt,int l,int r){
    printf("node %d [%d,%d] %d %d %d %d (%d %d %d %d)\n",rt,l,r,tree[rt].c0,tree[rt].c1,tree[rt].cq,tree[rt].cs,tree[rt].t0,tree[rt].t1,tree[rt].tq,tree[rt].ts);
}
void travel(int rt,int l,int r){
    int mid = (l + r) >> 1;
    if(ls(rt)) travel(ls(rt),l,mid);
    if(rs(rt)) travel(rs(rt),mid+1,r);
    prt(rt,l,r);
}

#define Mn -1000005
#define Mx +1000005
int dfs(int u){
    int rt = 0,temp;
    Q(rt);
    for(int v:son[u]){
        temp = dfs(v);
//        printf("clr at %d->%d\n",u,v);
        clr(temp,Mn,Mx,Mn,-w[u] - 1,1);
        clr(temp,Mn,Mx,w[u],Mx,0);
        rt = Merge(rt,temp);
    }
    upload(rt,Mn,Mx,Mn,-w[u] - 1,0,1,0);
    upload(rt,Mn,Mx,w[u],Mx,1,0,0);
    if(son[u].empty()) upload(rt,Mn,Mx,-w[u],w[u] - 1,0,0,1);
    else upload(rt,Mn,Mx,-w[u],w[u] - 1,0,0,0);
//    printf("travel %d\n",u);
//    travel(rt,Mn,Mx);
    return rt;
}

bool _ed;

void init(std::vector<int> _P, std::vector<int> _W) {
    cerr << (&_ed - &_st) / 1048576.0 << endl;
    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];
    }
    top = 60000000;
    rep(i,1,top) stk[i] = i;
    int rt = dfs(1);
//    printf("clr at 0->1\n");
    clr(rt,Mn,Mx,Mn,-1,1);
    clr(rt,Mn,Mx,0,Mx,0);
    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 tree7.cpp -o grader6.exe -Wall -Wshadow -O2 -std=c++14
*/