#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<int> s, p, w, l;
long long S;
vector<int> windist;
vector<array<pair<long long, int>, 25>> par;
void calcwindist(int x){
if(x == n)return;
if(windist[x])return;
calcwindist(w[x]);
windist[x] = windist[w[x]]+1;
}
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
n = n_;
s = s_, p = p_, w = w_, l = l_;
S = s[0];
windist.assign(n+1, 0);
for(int i = 0; i < n; i++){
calcwindist(i);
}
par.resize(n+1);
for(int i = 0; i < 25; i++){
par[n][i] = {0, n};
}
for(int i = 0; i < n; i++){
par[i][0] = {p[i], l[i]};
}
for(int i = 1; i < 25; i++){
for(int j = 0; j < n; j++){
par[j][i] = {par[j][i-1].first + par[par[j][i-1].second][i-1].first,
par[par[j][i-1].second][i-1].second};
}
}
return;
}
long long simulate(int x, int z) {
if(z >= S){
return z + S*windist[x];
}
for(int i = 24; i >= 0; i--){
if(x == n){
return z;
}
if(par[x][i].first + z < S){
z += par[x][i].first;
x = par[x][i].second;
}
}
if(x == n){
return z;
}
z += par[x][0].first;
x = par[x][0].second;
return z + S * windist[x];
}
