#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
#include "dungeons.h"
bool group3 = true, group2 = true;
ll t2[(ll)(4e5 + 7)][20][3];
vector<int> d3[(ll)(4e5 + 7)];
vector<ll> s, p, w, l;
ll n;
void build_t2(ll v, ll par){
t2[v][0][0] = par;
t2[v][0][1] = t2[v][0][2] = s[v];
for(int i = 1; i < 20; i++){
t2[v][i][0] = t2[t2[v][i - 1][0]][i - 1][0];
t2[v][i][1] = t2[v][i - 1][1] + t2[t2[v][i - 1][0]][i - 1][1];
t2[v][i][2] = max(t2[v][i - 1][2], t2[t2[v][i - 1][0]][i - 1][2]);
}
for(auto i: d3[v])
if(i != par)
build_t2(i, v);
}
void init(int n0, std::vector<int> s0, std::vector<int> p0, std::vector<int> w0, std::vector<int> l0){
n = n0;
s.resize(n + 1);
p.resize(n + 1);
w.resize(n + 1);
l.resize(n + 1);
for(ll i = 1; i <= n; i++){
s[i] = s0[i - 1], p[i] = p0[i - 1], w[i] = w0[i - 1], l[i] = l0[i - 1];
w[i]++, l[i]++;
}
for(int i = 1; i <= n; i++){
if(s[i] != s[1])
group3 = false;
if(s[i] != p[i])
group2 = false;
}
if(group2){
for(int i = 1; i <= n; i++)
d3[w[i]].push_back(i);
build_t2(n + 1, 0);
}
}
ll cor(ll x, ll z){
while(x != n + 1){
if(z >= s[x]){
z += s[x];
x = w[x];
}
else{
z += p[x];
x = l[x];
}
}
return z;
}
long long simulate(int x, int z){
x++;
if(!group3 && !group2)
return cor(x, z);
if(group2){
while(x != n + 1){
for(int i = 19; i >= 0; i--){
if(t2[x][i][0] != 0 && z >= t2[x][i][2]){
z += t2[x][i][1];
x = t2[x][i][0];
}
}
if(x != n + 1 && z < s[x]){
z += s[x];
x = l[x];
}
}
return z;
}
return 0;
}
/*
4 1
3 5 2 1
3 5 2 1
1 3 3 4
0 3 2 1
0 4
2 5
*/
