#include "tree.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mx=1000000;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],par[1100000],pr[1100000],leaf[1100000],leftsum[1100000],rightsum[1100000],good[1100000],c[1100000],chk[1100000],h[1100000],created[1100000];
ll lf;
vector<ll> v[1100000],u[1100000];
ll f(ll x)
{
    if(par[x]==x)
        return x;
    par[x]=f(par[x]);
    return par[x];
}
void g(ll x,ll y)
{
    x=f(x);
    y=f(y);
    if(x==y)
        return;
    if(h[x]>h[y])
    {
        swap(x,y);
    }
    h[y]+=h[x];
    par[x]=y;
    leaf[y]+=leaf[x];
}
void add(ll u,ll c)
{
    //printf("(%lld,%lld)\n",u,c);
    leftsum[u]+=c*u;
    rightsum[u]+=c;
}
void add_edge(ll x,ll y)
{
    if(pr[x]!=y)
        swap(x,y);
    leaf[f(y)]-=good[y];
    good[y]=0;
    leaf[f(y)]+=good[y];
}
void connect(ll x,ll t)
{
    ll i,s=1;
    for(i=0;i<v[x].size();i++)
    {
        if(chk[v[x][i]])
        {
            add(leaf[f(v[x][i])],created[f(v[x][i])]-t);
            add_edge(v[x][i],x);
        }
    }
    for(i=0;i<v[x].size();i++)
    {
        if(chk[v[x][i]])
        g(x,v[x][i]);
    }
    x=f(x);
    created[x]=t;

}
ll dfs1(ll x,ll y)
{
    ll i,s=0,z=1;
    pr[x]=y;
    for(i=0;i<v[x].size();i++)
    {
        if(v[x][i]==y)
            continue;
        z=0;
        s+=dfs1(v[x][i],x);
    }
    s+=z;
    return s;
}
void init(std::vector<int> P, std::vector<int> W) {
  n = (int)P.size();
  for(i=1;i<n;i++)
  {
      x=i+1;
      y=P[i]+1;
      v[x].push_back(y);
      v[y].push_back(x);
  }
  for(i=1;i<=n;i++)
  {
      h[i]=1;
      par[i]=i;
      good[i]=1;
  }
  for(i=0;i<n;i++)
  {
      a[i+1]=W[i];
  }
  lf=dfs1(1,0);
  for(i=1;i<=n;i++)
  {
      u[a[i]].push_back(i);
  }
  for(i=1000000;i>=1;i--)
  {
      for(auto xx:u[i])
      {
          chk[xx]=1;
          created[xx]=i;
          leaf[xx]=1;
          connect(xx,i);
      }
  }
  for(i=1;i<=n;i++)
  {
      if(chk[i]==0)
        continue;
      x=f(i);
      if(c[x])
        continue;
      c[x]=1;
      good[x]=1;
      add(leaf[x],created[x]);
  }
  for(i=1;i<=1000000;i++)
  {
      leftsum[i]+=leftsum[i-1];
      rightsum[i]+=rightsum[i-1];
  }
}

long long query(int L, int R) {
  l=L;
  r=R;
  s=l*lf;
  x=(r+l-1)/l;
  //printf("(%lld)",x);
  s+=(leftsum[mx]-leftsum[x-1])*l;
  s-=(rightsum[mx]-rightsum[x-1])*r;
  return s;
}