#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "cc"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r)
{
return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const int inf = 1e17+7;
const int mod2 =998244353;
//const ll base=67;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,
r2, center;
ll i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root, en;
ll el = 19;
bool ok[200001];
ll c[200001],par[200001];
vector<int> v[200001];
ll sz[200001],pl[1000014],sr[1000014],dc[1000014];
vector<int> vc;
void ddc(int x)
{
for(auto f:v[x])ddc(f);
if(v[x].size()==0)pl[1]++;
else
{
vc.pb(x);
}
}
struct dsuconcu
{
int get(int x)
{
if(par[x]!=x)par[x]=get(par[x]);
return par[x];
}
void noi(int x,int y)
{
y=get(y);
par[x]=y;
sz[y]+=sz[x];
}
} ds;
bool cmp(int x,int y)
{
return c[x]>c[y];
}
void init(std::vector<int> P, std::vector<int> W)
{
n=P.size();
for(int i=1; i<n; i++)
v[P[i]+1].pb(i+1);
for(int i=0; i<=n; i++)
dc[i]=1,par[i]=i,sz[i]=1;
for(int i=0; i<n; i++)
c[i]=W[i];
sort(vc.begin(),vc.end(),cmp);
ddc(1);
for(auto x:vc)
{
s4=0;
for(auto f:v[x])
s4+=sz[ds.get(f)],dem++;
pl[1]+=(dem-1)*c[x];
int hihi=P[ds.get(x)-1]+1;
s4--;
sr[dc[hihi]]++;
sr[dc[hihi]+s4]--;
pl[dc[hihi]+1]+=s4*c[x];
pl[dc[hihi]+s4+1]-=(dc[hihi]+s4)*c[x];
dc[hihi]+=s4;
for(auto f:v[i])ds.noi(f,x);
sz[ds.get(x)]--;
}
for(int i=1; i<=1e6; i++)pl[i]+=pl[i-1];
for(int i=1e6-1; i>=1; --i)sr[i]+=sr[i+1];
}
long long query(int l,int r)
{
int k=r/l+1;
return sr[k]*r+pl[k]*l;
}
