#include "dungeons.h"
#include <vector>
#include <cassert>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int B = 8;
const int LG = 30;
struct mdata {
int v;
ll mxdelta, gained;
};
mdata merge(const mdata &a, const mdata &b) {
return {b.v, max(a.mxdelta, b.mxdelta + a.gained), a.gained + b.gained};
}
int n;
vector<int> s, p, w, l;
vector<vector<vector<mdata>>> up;
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
n = n_ + 1;
s = s_;
s.push_back(0);
p = p_;
p.push_back(0);
w = w_;
w.push_back(n - 1);
l = l_;
l.push_back(n - 1);
up.resize(LG / B + 1, vector<vector<mdata>> (n, vector<mdata> (LG)));
for (int i = 0; i * B < LG; i++) {
int k = 1 << (i * B);
for (int v = 0; v < n; v++) {
if (s[v] < k) {
up[i][v][0] = {w[v], -INF, s[v]};
} else {
up[i][v][0] = {l[v], -s[v], p[v]};
}
}
for (int j = 1; j < LG; j++) {
for (int v = 0; v < n; v++) {
up[i][v][j] = merge(up[i][v][j - 1], up[i][up[i][v][j - 1].v][j - 1]);
}
}
}
}
ll simulate(int v, int z_) {
ll z = z_;
int k = 0;
while (v != n - 1) {
while (k < LG / B && (1 << ((k + 1) * B)) <= z) {
k++;
}
for (int i = LG - 1; i >= 0; i--) {
if (z + up[k][v][i].mxdelta < 0) {
z += up[k][v][i].gained;
v = up[k][v][i].v;
}
}
assert(z >= s[v]);
z += s[v];
v = w[v];
}
return z;
}
