#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>> liftWin;
vector<vector<info>> liftLos;
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));
liftWin.assign(N, vector<info>(ceil(log2(maxi) + 1)));
for (int i = 0; i < N; ++i)
{
liftWin[i][0].node = W[i];
liftWin[i][0].gain = S[i];
liftWin[i][0].needed = S[i];
}
for (int j = 1; j < sz(liftWin[0]); ++j)
{
for (int i = 0; i < N; ++i)
{
int mid = liftWin[i][j - 1].node;
if (mid == N)
liftWin[i][j] = liftWin[i][j - 1];
else
{
liftWin[i][j].node = liftWin[mid][j - 1].node;
liftWin[i][j].gain = liftWin[i][j - 1].gain + liftWin[mid][j - 1].gain;
liftWin[i][j].needed = max(liftWin[i][j - 1].needed, liftWin[mid][j - 1].needed - liftWin[i][j - 1].gain);
}
}
}
liftLos.assign(N, vector<info>(ceil(log2(maxi) + 1)));
for (int i = 0; i < N; ++i)
{
liftLos[i][0].node = L[i];
liftLos[i][0].gain = P[i];
liftLos[i][0].needed = S[i];
}
for (int j = 1; j < sz(liftLos[0]); ++j)
{
for (int i = 0; i < N; ++i)
{
int mid = liftLos[i][j - 1].node;
if (mid == N)
liftLos[i][j] = liftLos[i][j - 1];
else
{
liftLos[i][j].node = liftLos[mid][j - 1].node;
liftLos[i][j].gain = liftLos[i][j - 1].gain + liftLos[mid][j - 1].gain;
liftLos[i][j].needed = min(liftLos[i][j - 1].needed, liftLos[mid][j - 1].needed - liftLos[i][j - 1].gain);
}
}
}
return;
}
long long simulate(int x, int z)
{
ll ans = z;
while (x != N)
{
if (ans < S[x])
{
for (int j = sz(liftLos[x]) - 1; j >= 0; --j)
{
if (liftLos[x][j].needed > ans)
{
ans += liftLos[x][j].gain;
x = liftLos[x][j].node;
break;
}
}
}
else
{
for (int j = sz(liftWin[x]) - 1; j >= 0; --j)
{
if (liftWin[x][j].needed <= ans)
{
ans += liftWin[x][j].gain;
x = liftWin[x][j].node;
break;
}
}
}
}
return ans;
}
