#include <bits/stdc++.h>
#include "dungeons.h"
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 5e5 + 5;
const int bmax = 25;
struct Pointers {
int p[nmax][bmax];
ll sum[nmax][bmax];
int req[nmax][bmax];
void addlink(int node, int p_, int req_, int gain_) {
p[node][0] = p_;
sum[node][0] = gain_;
req[node][0] = req_;
}
void cascade(int n) {
for(int step = 1; step < bmax; step++) {
for(int i = 0; i <= n; i++) {
p[i][step] = p[p[i][step - 1]][step - 1];
sum[i][step] = sum[i][step - 1] + sum[p[i][step - 1]][step - 1];
req[i][step] = max({0LL, (ll)req[i][step - 1], (ll)req[p[i][step - 1]] - sum[i][step - 1]});
//cerr << p[i][step] << ' ';
}
}
return;
}
template<class CB> void walk(CB&& cb, int& node, ll& z) {
int bit = 0;
while(bit < bmax && cb(sum[node][bit], req[node][bit])) {
z += sum[node][bit];
node = p[node][bit];
bit++;
}
bit--;
while(bit >= 0 && cb(sum[node][bit], req[node][bit])) {
z += sum[node][bit];
node = p[node][bit];
bit--;
}
return;
}
};
namespace {
vector<signed> s, p, w, l;
int n;
}
Pointers winners;
void init(signed n_, std::vector<signed> s_, std::vector<signed> p_, std::vector<signed> w_, std::vector<signed> l_) {
n = n_;
s = s_;
p = p_;
w = w_;
l = l_;
for(int i = 0; i < n; i++) winners.addlink(i, w[i], s[i], s[i]);
winners.addlink(n, n, 0, 0);
winners.cascade(n);
return;
}
long long simulate(signed x_, signed z_) {
ll z = z_, x = x_;
while(x != n) {
winners.walk([&](ll sum, ll req) {
return z >= req;
}, x, z);
if(x == n) break;
if(s[x] > z) { z += p[x]; x = l[x]; }
else { z += s[x]; x = w[x]; assert(false); } // ????
}
return z;
}
#undef int
/**
Istenem! Nu poate fi real.
-- Surse verificate
*/
