#include "dungeons.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<vvpii> vvvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int N;
const ll INF = 1LL << 60;
vi S, P;
vi Svalues;
vector<int> W, L;
vi dpWin;
struct info
{
int node;
ll gain;
ll needed;
};
vector<vector<info>> lift;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l)
{
N = n;
S.resize(N), P.resize(N);
W = w, L = l;
for (int i = 0; i < N; ++i)
S[i] = s[i], P[i] = p[i];
int maxi = *max_element(all(S));
lift.assign(N, vector<info>(ceil(log2(maxi) + 1)));
for (int i = 0; i < N; ++i)
{
lift[i][0].node = W[i];
lift[i][0].gain = S[i];
lift[i][0].needed = S[i];
}
for (int j = 1; j < sz(lift[0]); ++j)
{
for (int i = 0; i < N; ++i)
{
int mid = lift[i][j - 1].node;
if (mid == N)
lift[i][j] = lift[i][j - 1];
else
{
lift[i][j].node = lift[mid][j - 1].node;
lift[i][j].gain = lift[i][j - 1].gain + lift[mid][j - 1].gain;
lift[i][j].needed = max(lift[i][j - 1].needed, lift[mid][j - 1].needed - lift[i][j - 1].gain);
}
}
}
return;
}
long long simulate(int x, int z)
{
ll ans = z;
while (x != N)
{
if (ans < lift[x][0].needed)
{
ans += P[x];
x = L[x];
}
else
{
for (int j = sz(lift[x]) - 1; j >= 0; --j)
{
if (lift[x][j].needed <= ans)
{
ans += lift[x][j].gain;
x = lift[x][j].node;
break;
}
}
}
}
return ans;
}
