#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
const int maxn=2e5+5;
const int maxw=1e6+5;
int n,t,u;
int in[maxn],out[maxn],leaf[maxn],ans[maxn],ans2[maxn];
pii cnt[maxn];
vector<pii> ord;
vector<int> adj[maxn];
vector<signed> p,w;
int tree[maxn*4],lazy[maxn*4];
void pushdown(int l,int r,int idx){
if(lazy[idx]){
tree[idx]=lazy[idx];
if(l!=r){
lazy[idx*2]=lazy[idx];
lazy[idx*2+1]=lazy[idx];
}
lazy[idx]=0;
}
}
void update(int l,int r,int idx,int u,int v,int val){
pushdown(l,r,idx);
if(v<l||r<u) return;
if(u<=l&&r<=v){
lazy[idx]=val;
pushdown(l,r,idx);
return;
}
int m=l+((r-l)>>1);
update(l,m,idx*2,u,v,val);
update(m+1,r,idx*2+1,u,v,val);
tree[idx]=max(tree[idx*2],tree[idx*2+1]);
}
int get(int l,int r,int idx,int u,int v){
pushdown(l,r,idx);
if(v<l||r<u) return -1;;
if(u<=l&&r<=v) return tree[idx];
int m=l+((r-l)>>1);
return max(get(l,m,idx*2,u,v), get(m+1,r,idx*2+1,u,v));
}
void dfs(int x){
in[x]=t++;
if(!adj[x].size()) leaf[x]=1;
for(int c:adj[x]){
dfs(c);
leaf[x]+=leaf[c];
}
out[x]=t;
}
void init(vector<signed> P,vector<signed> W){
p=P;w=W;
n=p.size();
for(int i=0;i<n;i++){
if(i) adj[p[i]].pb(i);
ord.pb({w[i],i});
}
sort(ord.begin(),ord.end());
dfs(0);
cnt[leaf[0]]={1,0};
for(int k=0;k<maxw;k++){
//cout<<"---------------\n";
while(u<n&&ord[u].f<=k){
int cur=ord[u].s;
u++;
int p=get(0,n,1,in[cur],in[cur]);
// remove parent
if(cnt[leaf[p]].s!=k) ans[leaf[p]]+=cnt[leaf[p]].f*(k-cnt[leaf[p]].s);
cnt[leaf[p]].f--;
cnt[leaf[p]].s=k;
// add parent
if(p!=cur){
leaf[p]-=leaf[cur]-1;
if(cnt[leaf[p]].s!=k) ans[leaf[p]]+=cnt[leaf[p]].f*(k-cnt[leaf[p]].s);
cnt[leaf[p]].f++;
cnt[leaf[p]].s=k;
}
// add children
for(int c:adj[cur]){
if(w[c]<=k) continue;
update(0,n,1,in[c],out[c]-1,c);
if(cnt[leaf[c]].s!=k) ans[leaf[c]]+=cnt[leaf[c]].f*(k-cnt[leaf[c]].s);
cnt[leaf[c]].f++;
cnt[leaf[c]].s=k;
}
// cout<<cur<<' '<<p<<'\n';
// for(int i=0;i<10;i++){
// cout<<cnt[i].f<<' ';
// }cout<<'\n';
// for(int i=0;i<10;i++){
// cout<<cnt[i].s<<' ';
// }cout<<'\n';
// for(int i=0;i<10;i++){
// cout<<ans[i]<<' ';
// }cout<<'\n';cout<<'\n';
}
}
for(int i=1;i<maxn;i++){
ans2[i]=ans[i]*i;
ans[i]+=ans[i-1];
ans2[i]+=ans2[i-1];
}
}
int query(signed L, signed R) {
int s=R/L;
s=min(maxn-1,s);
return ans2[maxn-1]*L+(ans2[maxn-1]-ans2[s])*L-(ans[maxn-1]-ans[s])*L;
}
