#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define pll pair<ll,ll>
const int B = 20;
const int mxn = 4e5+10;
int par[mxn][B];
ll dp[mxn][B];
ll sum[mxn][B];
ll pref[mxn];
int N;
int str[mxn],win[mxn],lose[mxn],cost[mxn];
struct JELLY{
int par[mxn][B];
ll sum[mxn][B];
JELLY(){
memset(par,-1,sizeof(par));
memset(sum,0,sizeof(sum));
}
void build(){
for(int i = 1;i<B;i++){
for(int j = 0;j<N;j++){
int pre = par[j][i-1];
if(pre == -1)continue;
par[j][i] = par[par[j][i-1]][i-1];
sum[j][i] = sum[j][i-1]+sum[pre][i-1];
}
}
return;
}
};
JELLY jel;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
memset(par,-1,sizeof(par));
N = n;
for(int i = 0;i<N;i++){
str[i] = s[i];
cost[i] = p[i];
win[i] = w[i];
lose[i] = l[i];
}
win[N] = lose[N] = N;
for(int i = 0;i<B;i++){
par[N][i] = -1;
}
for(int i = N-1;i>=0;i--){
pref[i] = str[i]+pref[win[i]];
dp[i][0] = str[i]+pref[i];
par[i][0] = win[i];
sum[i][0] = str[i];
for(int j = 1;j<B;j++){
int pre = par[i][j-1];
if(pre == -1)continue;
par[i][j] = par[par[i][j-1]][j-1];
dp[i][j] = max(dp[i][j-1],dp[par[i][j-1]][j-1]);
sum[i][j] = sum[i][j-1]+sum[par[i][j-1]][j-1];
}
}
for(int i = 0;i<N;i++){
jel.sum[i][0] = cost[i];
jel.par[i][0] = lose[i];
}
jel.build();
/*
cerr<<"PAR: "<<endl;for(int i = 0;i<N;i++){
for(int j = 0;j<B;j++)cerr<<par[i][j]<<' ';cerr<<endl;
}
cerr<<"DP: "<<endl;for(int i = 0;i<N;i++){
for(int j = 0;j<B;j++)cerr<<dp[i][j]<<' ';cerr<<endl;
}
cerr<<"SUM: "<<endl;for(int i = 0;i<N;i++){
for(int j = 0;j<B;j++)cerr<<sum[i][j]<<' ';cerr<<endl;
}
cerr<<"PREF: "<<endl;for(int i = 0;i<=N;i++)cerr<<pref[i]<<' ';cerr<<endl;
cerr<<"JEL PAR: "<<endl;for(int i = 0;i<N;i++){
for(int j = 0;j<B;j++)cerr<<jel.par[i][j]<<' ';cerr<<endl;
}
*/
return;
}
long long simulate(int x, int z) {
int now = x;
ll val = z;
for(int i = B-1;i>=0;i--){
int pre = jel.par[now][i];
if(pre == -1)continue;
if(val+jel.sum[now][i]<str[0]){
val += jel.sum[now][i];
now = jel.par[now][i];
//cerr<<"LOSE: "<<i<<' '<<now<<','<<val<<endl;
}
}
if(val<str[0]){
val += cost[now];
now = lose[now];
}
val += pref[now];
return val;
}
