#include "dungeons.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define len(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = (int)4e5 + 10;
vector<int>s,p,w,l;
int n;
vector < int > g[N];
int used[N];
ll ans[N];
int mxS;
pair < int , ll >want[N];
vector<pair<int,ll>> want1[N];
void dfs(int v){
if(used[v])return;
used[v] = 1;
if(v == n)
return;
dfs(w[v]);
ans[v] = ans[w[v]] + s[v];
}
ll pref[N];
int sid[N];
int fen[N];
int id[N];
int h[N];
vector<int> SID[N];
vector<vector<pair<int,int>>>keep;
vector<pair<int,int>>was;
void modify(int x , int val){
keep.pb({});
for(; x < N; x += x &- x){
keep.back().pb({x , fen[x]});
fen[x] = max(fen[x] , val);
}
}
int get(int x){
int mx = 0;
for(; x > 0 ; x -= x &- x)
mx = max(mx , fen[x]);
return mx;
}
void rollback(){
for(auto u : keep.back())
fen[u.fi] = u.se;
keep.pop_back();
}
vector<int>pred;
void dfs1(int v, int H, ll P){
h[v] = H;
pref[v] = P + s[v];
/// in get
pred.pb(v);
// cerr << " LOL " << v << ' ' << SID[v] << ' ' << sid[v] << endl;
if(v != n){
int hh = get(N-1-sid[v]-1);
int pp = pred[hh];
want[v] = {pp , pref[v] - pref[pp]};
int lst = 0;
want1[v].resize(len(SID[v]));
for(auto SI : SID[v]){
if(sid[v] > SI){
want1[v][lst] = {v , 0};
}else{
hh = get(N-1-SI-1);
pp = pred[hh];
want1[v][lst] = {pp , pref[v] - pref[pp]};
}
lst++;
}
}
// if(v != n){
modify(N-1-sid[v], h[v]);
// }
for(auto u : g[v]){
dfs1(u , H+1, pref[v]);
}
// if(v != n)
rollback();
pred.pop_back();
}
bool eq = 0;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
s = S;
p = P;
w = W;
l = L;
n = N;
eq = 1;
for(int x = 0 ; x < n; ++x)
if(p[x] != s[x])
eq = 0;
mxS = *max_element(all(s));
for(int i = 0 ; i < n; ++i){
g[w[i]].pb(i);
}
for(int i = 0 ; i < n; ++i){
dfs(i);
}
s.pb((int)1e7+1);
vector<int>srt;
for(int x = 0 ; x <= n; ++x)
srt.pb(s[x]);
sort(all(srt));
srt.erase(unique(all(srt)) , srt.end());
for(int x = 0 ; x <= n; ++x)
sid[x] = lower_bound(all(srt), s[x]) - srt.begin();
for(int x = 0 ; x < n; ++x){
/// w[x]
SID[l[x]].pb(sid[x]);
}
for(int x = 0; x < n; ++x)
sort(all(SID[x]));
dfs1(n , 0 , 0);
return;
}
long long simulate(int x, int Z) {
long long z = Z;
while(x != n){
if(z >= mxS){
z += ans[x];
x = n;
continue;
}
if(z >= s[x]){
z += want[x].se;
x = want[x].fi;
continue;
}
// cerr << " GO by L\n" << x << ' ' << l[x] << ' ' << p[x] << ' ' << s[x] << endl;
int P = sid[x];
z += p[x], x = l[x];
/// and now we want to go for it
if(eq){
if(x != n){
int f = lower_bound(all(SID[x]), P) - SID[x].begin();
z += want1[x][f].se;
x = want1[x][f].fi;
}
}
}
return z;
}
