#include "dungeons.h"
#include <vector>
//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugp(x,y) cerr<<#x<<' '<<#y<<" is "<<x<<' '<<y<<endl;
#define debugl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p<<" ";cerr<<endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<" , ";cerr<<endl;
//#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define rdint(x,y) rnd()%(y-x+1)+x
//const int inf=4e18+5;
const int mod=1e9+7;
const int mod2=998244353;
const int mod3=1e9+9;
const int maxn=5e4+5;
const int mk=24;
vi ss,pp,ww,ll;
int nn,ts;
int par[maxn][mk];
int ps[maxn][mk];
int d[maxn];//dis from end
void dcmp(){
for(int k=1;k<mk;k++){
for(int i=0;i<=nn;i++){
par[i][k]=par[par[i][k-1]][k-1];
ps[i][k]=ps[i][k-1]+ps[par[i][k-1]][k-1];
//if(k==1&&i==0)debug(ps[i][k])
}
par[nn][k]=nn;
}
}
#define int long long
pii bsta(int x,int z){
//debug(z)
//debug(z)
for(int k=mk-1;k>=0;k--){
if(par[x][k]!=nn&&z+ps[x][k]<ts){
//debug(ps[x][k])
z+=ps[x][k];
//debug(z)
x=par[x][k];
}
}
return {par[x][0],z+ps[x][0]};
}
#undef int
vi adj[maxn];
void dfs(int x){
d[x]=d[ww[x]]+1;
for(auto i:adj[x])dfs(i);
}
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
ss=s;
ts=s[0];
pp=p;
ww=w;
ll=l;
nn=n;
for(int i=0;i<n;i++){
par[i][0]=l[i];
ps[i][0]=p[i];
}
par[n][0]=n;
for(int i=0;i<n;i++){
adj[w[i]].pb(i);
}
dcmp();
for(auto i:adj[n])dfs(i);
return;
}
long long simulate(int x, int z) {
auto [nx,nz]=bsta(x,z);
if(z>=ts)nx=x,nz=z;
//debug(ps[0][0])
//debugp(nx,nz)
//debug(d[nx])
return nz+d[nx]*ts;
}
