#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>w,l,s,p;
struct pom{
long long sum=0,smax=0,nxt=0;
};
vector<vector<pom>>lca;
void init(int N,vector<int> S,vector<int> P,vector<int> W,vector<int> L) {
n=N;
l=L;
s=S;
p=P;
w=W;
lca.resize(n+1,vector<pom>(25));
s.push_back(0);
l.push_back(n);
w.push_back(n);
p.push_back(0);
for(int j=0;j<25;j++)
{
for(int i=0;i<=n;i++)
{
if(j==0)
{
lca[i][j].nxt=w[i];
lca[i][j].sum=s[i];
lca[i][j].smax=s[w[i]]-s[i];
}
else
{
int a=lca[i][j-1].nxt;
lca[i][j].nxt=lca[a][j-1].nxt;
lca[i][j].sum=lca[i][j-1].sum+lca[a][j-1].sum;
lca[i][j].smax=max(lca[i][j-1].smax,lca[a][j-1].smax-lca[i][j-1].sum);
}
}
}
return;
}
long long simulate(int x, int z) {
long long sum=z;
while(x!=n)
{
if(sum>=s[x])
{
for(int i=24;i>=0;i--)
{
if(sum>=lca[x][i].smax)
{
sum+=lca[x][i].sum;
x=lca[x][i].nxt;
}
}
}
else
{
sum+=p[x];
x=l[x];
}
}
return sum;
}
