#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#include "dungeons.h"
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;
//all ops have same strength
//once cur>=s[i], keeps going until win. get dist from n?
//while cur<s[i], keeps hopping....
//bsearch how many times it hops to get>=s[i]? at most 1e7
//store 2^ith parent -> p[layer][id]=node, gain in strength to get there
//what 2^ith parent is n?
LL n;
const LL MAXN=4e5+5, LOG=24;
LL p[MAXN][LOG][2]; //position, gain in strength
LL s[MAXN], w[MAXN];
LL d[MAXN]; //dist from n
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n=(LL)N;
FOR(i,n){
s[i]=(LL)S[i];
w[i]=(LL)W[i];
p[i][0][0]=(LL)L[i];
p[i][0][1]=(LL)P[i];
}
FOR(j,LOG){
p[n][j][0]=n;
p[n][j][1]=0;
}
FR(j,1,LOG) FOR(i,n){
p[i][j][0]=p[p[i][j-1][0]][j-1][0];
p[i][j][1]=p[p[i][j-1][0]][j-1][1]+p[i][j-1][1];
}
for (int i=n-1; i>=0; i--) d[i]=d[w[i]]+1;
return;
}
long long simulate(int X, int Z) {
LL x=(LL)X, z=(LL)Z;
LL cur=z, pos=x;
if (z<s[0]){
LL lo=0, hi=(LL)(1e7+7);
while (lo<hi){
LL mid=(lo+hi)/2;
LL t=z, pp=x;
for (int j=0; j<=LOG; j++){
if (mid&(1LL<<j)){
t+=p[pp][j][1];
pp=p[pp][j][0];
}
}
if (t>=s[0] || pp==n) hi=mid;
else lo=mid+1;
}
for (int j=0; j<=LOG; j++){
if (lo&(1LL<<j)){
cur+=p[pos][j][1];
pos=p[pos][j][0];
}
}
//cout<<lo<<": "<<cur<<" "<<pos<<"\n";
}
cur+=d[pos]*s[0];
return cur;
}
