#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=200010, M=1000010;
int n, p[N], g[N], a[N];
bool w[N];
vector<pair<int, int>> v;
ll x[N], y[N], l[N];
ll tot, c[M], s[M];
vector<int> adj[N];
int Find(int x) {return g[x]?(g[x]=Find(g[x])):x;}
void Union(int u, int v, ll t) {
u=Find(u), v=Find(v);
if(l[u]) tot+=x[u]*(l[u]-t), c[y[u]]+=(l[u]-t), s[y[u]]+=y[u]*(l[u]-t);
if(l[v]) tot+=x[v]*(l[v]-t), c[y[v]]+=(l[v]-t), s[y[v]]+=y[v]*(l[v]-t);
x[v]+=x[u], y[v]+=y[u], l[v]=t, g[u]=v;
}
void init(vector<int> P, vector<int> W) {
n=P.size();
for(int i=1; i<=n; i++) a[i]=W[i-1], v.push_back({a[i], i});
for(int i=2; i<=n; i++) p[i]=P[i-1]+1, adj[p[i]].push_back(i);
for(int i=1; i<=n; i++) if(adj[i].empty()) x[i]++, y[i]++;
sort(v.rbegin(), v.rend());
for(auto [t, k]:v) if(t) {
w[k]=1;
if(w[p[k]]) Union(k, p[k], t), y[Find(k)]--;
for(int j:adj[k]) if(w[j]) Union(k, j, t);
for(int j:adj[k]) if(!w[j]) y[Find(k)]++;
l[Find(k)]=t;
}
for(int i=1; i<=n; i++) if(w[i] && Find(i)==i) {
tot+=x[i]*l[i], c[y[i]]+=l[i], s[y[i]]+=y[i]*l[i];
}
for(int i=M-2; i>=1; i--) c[i]+=c[i+1], s[i]+=s[i+1];
}
ll query(int L_, int R_) {
ll L=L_, R=R_;
return tot*L+s[(R+L-1)/L]*L-c[(R+L-1)/L]*R;
}
