#include "dungeons.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <cstdio>
int hp[400005];
int addw[400005];
int addl[400005];
int muchw[400005];
int muchl[400005];
int dist[400005];
int bl[26][400005];
long long costbl[26][400005];
int nmax;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
nmax=n;
for(int i=1;i<=n;i++)
{
hp[i]=s[i-1];
addw[i]=s[i-1];
addl[i]=p[i-1];
muchw[i]=w[i-1]+1;
muchl[i]=l[i-1]+1;
}
dist[n+1]=0;
for(int i=n;i>=1;i--)
{
dist[i]=dist[muchw[i]]+1;
}
addl[n+1]=0;
bl[0][n+1]=n+1;
for(int i=1;i<=n+1;i++)
{
costbl[0][i]=addl[i];
bl[0][i]=muchl[i];
}
for(int i=1;i<=24;i++)
{
for(int j=1;j<=n+1;j++)
{
bl[i][j]=bl[i-1][bl[i-1][j]];
costbl[i][j]=costbl[i-1][j]+costbl[i-1][bl[i-1][j]];
}
}
return;
}
long long simulate(int x, int z) {
long long z2=z;
x++;
if(z2>=hp[nmax])
{
return z2+dist[x]*hp[nmax];
}
for(int i=24;i>=0;i--)
{
int nxt=bl[i][x];
long long nxtval=costbl[i][x];
if(z2+nxtval<hp[nmax])
{
z2=z2+costbl[i][x];
x=bl[i][x];
}
}
z2=z2+costbl[0][x];
x=bl[0][x];
return z2+dist[x]*hp[nmax];
}
