#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 400001;
const int MAX_LOG = 25; // 2^24 > 10^7
int n, p[MAX_N], l[MAX_N];
struct {
int end;
long long gained;
long long min; // min(sum(gained) - opponent)
} dp[MAX_N][MAX_LOG];
void init(int n_, vector<int> s, vector<int> p_,
vector<int> w, vector<int> l_) {
n = n_;
copy_n(p_.begin(), n, p);
copy_n(l_.begin(), n, l);
l[n] = n;
for (int j = 0; j < MAX_LOG; j++)
for (int i = 0; i <= n; i++) {
auto& x = dp[i][j];
if (j == 0)
if (i == n) {
x.end = n;
x.gained = x.min = 0;
} else {
x.end = w[i];
x.gained = s[i];
x.min = -s[i];
}
else {
auto& a = dp[i][j - 1];
auto& b = dp[a.end][j - 1];
x.end = b.end;
x.gained = a.gained + b.gained;
x.min = min(a.min, a.gained + b.min);
}
}
}
// because p[i] = s[i], every time we lose, our strength doubles
// => we only lose log(max(s)) times. use binary lifting to find next
// fight we lose
long long simulate(int at, int strength) {
// do we lose any of the next 2^j fights?
auto lose = [&](int j) {
return strength + dp[at][j].min < 0;
};
while (at != n) {
// jump until we lose
for (int j = MAX_LOG - 1; j >= 0; j--)
if (!lose(j)) {
auto& x = dp[at][j];
at = x.end;
strength += x.gained;
}
// lose (if at = n, this adds 0)
strength += p[at]; // = s[at] > strength
at = l[at];
}
return strength;
}
