#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10, maxlog = 25;
int n, w[maxn], l[maxn];
ll s[maxn], p[maxn];
vector < int > child[maxn];
struct jump
{
ll sum, max_strenght;
int ver;
};
jump dp[maxlog][maxn], fp[maxlog][maxn];
void dfs(int v)
{
dp[0][v].ver = w[v];
dp[0][v].sum = s[v];
dp[0][v].max_strenght = s[v];
for (int j = 1; j < maxlog; j ++)
{
dp[j][v].sum = dp[j - 1][v].sum + dp[j - 1][dp[j - 1][v].ver].sum;
dp[j][v].ver = dp[j - 1][dp[j - 1][v].ver].ver;
dp[j][v].max_strenght = max(dp[j - 1][v].max_strenght, dp[j - 1][dp[j - 1][v].ver].max_strenght);
}
for (int u : child[v])
{
dfs(u);
}
}
bool all_same = true;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
n = N;
for (int i = 0; i < n; i ++)
{
s[i] = S[i];
p[i] = P[i];
w[i] = W[i];
l[i] = L[i];
child[w[i]].push_back(i);
}
for (int i = 1; i < n; i ++)
{
if (s[i] != s[i - 1])
all_same = false;
}
for (int j = 0; j < maxlog; j ++)
dp[j][n].ver = n;
w[n] = n;
l[n] = n;
s[n] = 1e15;
dfs(n);
for (int i = 0; i <= n; i ++)
{
fp[0][i].ver = l[i];
fp[0][i].sum = p[i];
}
for (int j = 1; j < maxlog; j ++)
{
for (int i = 0; i < n; i ++)
{
fp[j][i].ver = fp[j - 1][fp[j - 1][i].ver].ver;
fp[j][i].sum = fp[j - 1][fp[j - 1][i].ver].sum + fp[j - 1][i].sum;
}
}
return;
}
long long simulate(int x, int z)
{
ll strength = z;
while(x != n)
{
if (strength >= s[x])
{
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (dp[bit][x].max_strenght <= strength)
{
strength += dp[bit][x].sum;
x = dp[bit][x].ver;
}
}
///cout << x << endl;
}
else
{
if (all_same)
{
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (strength + fp[bit][x].sum < s[0])
{
strength += fp[bit][x].sum;
x = fp[bit][x].ver;
}
}
}
strength += p[x];
x = l[x];
}
}
return strength;
}
