#include "dungeons.h"
#include <bits/stdc++.h>
#define SIZE 400005
#define ll long long
using namespace std;
int n;
ll s[SIZE] , p[SIZE][26];
int w[SIZE] , l[SIZE][26];
ll S;
ll dp[SIZE];
ll dfs(int here) {
if (here==n) return dp[here]=0;
if (dp[here] != -1) return dp[here];
return dp[here] = dfs(w[here])+S;
}
void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
n = _n;
for (int i = 0; i < n; i++) s[i] = _s[i], p[i][0] = _p[i], w[i] = _w[i] , l[i][0] = _l[i];
S = s[0];
for (int j = 1; j < 26; j++) {
for (int i = 0; i < n; i++) {
p[i][j] = p[i][j-1]+p[l[i][j-1]][j-1];
l[i][j] = l[l[i][j-1]][j-1];
}
}
memset(dp , -1 , sizeof(dp));
for (int i = 0; i < n; i++) {
if (dp[i]==-1) dfs(i);
}
return;
}
bool f(int x , int cnt , int z) {
ll HP = z*1LL;
for (int j = 25; j >= 0; j--) {
if (cnt&(1<<j)) {
HP += p[x][j];
x = l[x][j];
}
}
if (HP >= S) return true;
return false;
}
long long simulate(int x, int z) {
ll HP = z*1LL;
int lo = 0 , hi = 2e7;
while(lo < hi) {
int mid = (lo+hi)/2;
if (f(x , mid , z)) hi = mid;
else lo = mid+1;
}
for (int j = 25; j >= 0; j--) {
if (lo&(1<<j)) {
HP += p[x][j];
x = l[x][j];
}
}
assert(HP >= S);
HP += dp[x];
return HP;
}
