#include "tree.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
int N, par[MAXN], siz[MAXN], cost[MAXN];
ll A[MAXN], B[MAXN];
vector <int> adj[MAXN];
vector <pii> S;
void pref(int k,ll w) {
A[k-1] += k*w;
B[k-1] -= w;
}
int find(int x) {
if (par[x] == x) {
return x;
}
return par[x] = find(par[x]);
}
void join(int x,int y,int z) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
pref(siz[x],cost[x]-z);
pref(siz[y],cost[y]-z);
siz[x] += siz[y];
cost[x] = z;
par[y] = x;
}
void init(vector<int> P,vector<int> W) {
N = P.size();
for (int i=1;i<N;i++) {
adj[P[i]].push_back(i);
}
for (int i=0;i<N;i++) {
par[i] = i;
siz[i] = 1;
if (adj[i].empty()) {
A[N] += W[i];
}
else if (W[i] != 0) {
S.push_back({W[i],i});
}
}
sort(S.begin(),S.end());
reverse(S.begin(),S.end());
for (auto p : S) {
int w = p.fi;
int u = p.se;
for (int v : adj[u]) {
join(u, v, w);
}
siz[find(u)]--;
}
for (int i=0;i<N;i++) {
if (find(i) == i) {
pref(siz[i], cost[i]);
}
}
for (int i=N;i>=1;i--) {
A[i] += A[i+1];
B[i] += B[i+1];
}
}
long long query(int L, int R) {
int k = min(N,R/L);
return L*A[k]+R*B[k];
}
