#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vint = vector<int>;
constexpr ll maxn = 400005;
constexpr ll loge = 30;
//binlift
ll par[maxn][loge];
ll gain[maxn][loge];
ll allwin[maxn];
ll n;
vll l;
vll p;
vll s;
vll w;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n=N;
for(auto num:L)
l.push_back(num);
for(auto num:P)
p.push_back(num);
for(auto num:S)
s.push_back(num);
for(auto num:W)
w.push_back(num);
par[n][0]=n;
gain[n][0]=0;
for(ll i=0;i<n;i++)
{
par[i][0]=l[i];
gain[i][0]=p[i];
}
for(ll j=1;j<loge;j++)
{
for(ll i=0;i<=n;i++)
{
par[i][j]=par[par[i][j-1]][j-1];
gain[i][j]=gain[par[i][j-1]][j-1]+gain[i][j-1];
}
}
allwin[n]=0;
for(ll i=n-1;i>=0;i--)
allwin[i]=s[i]+allwin[w[i]];
return;
}
long long simulate(int x, int owo)
{
ll strength=owo;
ll ptr = loge-1;
while(x!=n && ptr>=0 && strength<s[x])
{
if(par[x][ptr]!=n && strength+gain[x][ptr]<s[par[x][ptr]])
{
//cerr << ptr << ": " << strength << "," << gain[x][ptr] << '\n';
strength+=gain[x][ptr];
x=par[x][ptr];
}
ptr--;
}
//cerr << par[0][0] << '\n';
while(x!=n)
{
if(strength<s[x])
{
strength+=p[x];
x=l[x];
}
else
{
strength+=allwin[x];
x=n;
}
}
//cerr << *max_element(allwin,allwin+n) << '\n';
return strength;
}
