#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long mm=24,inf=1e18;
long long n,nv,nn,a[400069],a2[400069],pr[400069],pr2[400069],ca[mm+1][400069],cpr[mm+1][400069],cmn[mm+1][400069],vi[400069],ex[400069],bl[mm+1][400069],dh[400069],wg[mm+1][400069],mna[mm+1][400069],cywg[mm+1][400069],cymn[mm+1][400069];
vector<long long> al[400069];
bitset<400069> spc;
void dfs(long long cr,long long x,long long sr)
{
long long i,sz=al[x].size(),l,l2,l3;
l=cpr[cr][x]*(x!=sr);
l2=bl[cr][l];
l3=bl[cr][l2];
if(l&&l2&&l3&&dh[l2]-dh[l3]==dh[l]-dh[l2])
{
bl[cr][x]=l3;
wg[cr][x]=ca[cr][x]+wg[cr][l]+wg[cr][l2];
mna[cr][x]=min({cmn[cr][x],mna[cr][l]-ca[cr][x],mna[cr][l2]-wg[cr][l]-ca[cr][x]});
}
else
{
bl[cr][x]=l;
wg[cr][x]=ca[cr][x];
mna[cr][x]=cmn[cr][x];
}
for(i=0;i<sz;i++)
{
l=al[x][i];
if(l==sr)
{
continue;
}
dh[l]=dh[x]+1;
dfs(cr,l,sr);
}
}
void init(int on,vector<int> oa,vector<int> oa2,vector<int> opr,vector<int> opr2)
{
long long i,j,r,k,p,sm,mn;
n=on;
for(i=1;i<=n;i++)
{
a[i]=oa[i-1];
a2[i]=oa2[i-1];
pr[i]=opr[i-1]+1;
pr2[i]=opr2[i-1]+1;
}
pr[n+1]=n+1;
pr2[n+1]=n+1;
for(i=0;i<=mm;i++)
{
for(j=1;j<=n+1;j++)
{
if(a[j]<1ll<<i)
{
ca[i][j]=a[j];
cpr[i][j]=pr[j];
cmn[i][j]=inf;
}
else
{
ca[i][j]=a2[j];
cpr[i][j]=pr2[j];
cmn[i][j]=a[j];
}
al[j].clear();
vi[j]=0;
}
spc.reset();
for(j=1;j<=n+1;j++)
{
al[cpr[i][j]].push_back(j);
}
nv=0;
for(j=1;j<=n+1;j++)
{
nv++;
for(p=j;!vi[p];p=cpr[i][p])
{
vi[p]=nv;
}
if(vi[p]==nv)
{
nn=0;
for(;!spc[p];p=cpr[i][p])
{
spc[p]=1;
nn++;
ex[nn]=p;
}
k=ex[nn];
bl[i][k]=0;
dh[k]=0;
dfs(i,k,k);
sm=0;
mn=inf;
for(r=nn;r;r--)
{
k=ex[r];
sm+=ca[i][k];
mn=min(mn-ca[i][k],cmn[i][k]);
}
k=ex[1];
cywg[i][k]=sm;
cymn[i][k]=mn;
}
}
}
}
long long simulate(int x,int w)
{
long long i,ww,ub,c;
x++;
ww=w;
for(i=0;i<=mm;i++)
{
ub=(1ll<<i+1)-1;
if(i==mm)
{
ub=inf;
}
for(;x!=n+1&&ww<=ub;)
{
for(;1;)
{
if(!bl[i][x])
{
break;
}
if(bl[i][x]!=n+1&&ww+wg[i][x]<=ub&&ww<mna[i][x])
{
ww+=wg[i][x];
x=bl[i][x];
}
else if(cpr[i][x]!=n+1&&ww+ca[i][x]<=ub&&ww<cmn[i][x])
{
ww+=ca[i][x];
x=cpr[i][x];
}
else
{
break;
}
}
if(ww>=a[x])
{
ww+=a[x];
x=pr[x];
}
else
{
ww+=a2[x];
x=pr2[x];
}
if(x!=n+1&&ww<=ub)
{
c=max(min(ub,cymn[i][x])-ww,0ll)/cywg[i][x];
ww+=cywg[i][x]*c;
}
}
}
return ww;
}
