#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
namespace
{
struct node
{
// value, min required initial value
ll v, m;
};
node merge(node l, node r)
{
auto [lv, lm] = l;
auto [rv, rm] = r;
return node{lv + rv, max(lm, rm - lv)};
}
const int P = 25;
int n, m;
int id[400001][P];
node go[400001][P];
vector<int> s, p, w, l;
}
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;
for (int i = 0; i < n; i++)
go[i][0] = node{s[i], s[i]}, id[i][0] = w[i];
go[n][0] = node{0, 0}, id[n][0] = n;
for (int k = 0; k + 1 < P; k++)
for (int i = 0; i <= n; i++)
go[i][k + 1] = merge(go[i][k], go[id[i][k]][k]), id[i][k + 1] = id[id[i][k]][k];
return;
}
ll simulate(int x, int _z)
{
ll z = _z;
while (x != n)
{
for (int k = P - 1; k >= 0; k--)
if (go[x][k].m <= z)
z += go[x][k].v, x = id[x][k];
if (x != n)
{
z += p[x];
x = l[x];
}
}
return z;
}
