#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10, maxlog = 25;
int n, w[maxn], l[maxn];
ll s[maxn], p[maxn];
vector < int > child[maxn];
struct jump
{
ll sum, max_strenght;
int ver;
};
jump dp[maxlog][maxn], fp[maxlog][maxn];
void dfs(int v)
{
dp[0][v].ver = w[v];
dp[0][v].sum = s[v];
dp[0][v].max_strenght = s[v];
for (int j = 1; j < maxlog; j ++)
{
dp[j][v].sum = dp[j - 1][v].sum + dp[j - 1][dp[j - 1][v].ver].sum;
dp[j][v].ver = dp[j - 1][dp[j - 1][v].ver].ver;
dp[j][v].max_strenght = max(dp[j - 1][v].max_strenght, dp[j - 1][dp[j - 1][v].ver].max_strenght);
}
for (int u : child[v])
{
dfs(u);
}
}
bool all_same = true;
set < ll > st;
vector < ll > values;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
n = N;
for (int i = 0; i < n; i ++)
{
s[i] = S[i];
p[i] = P[i];
w[i] = W[i];
l[i] = L[i];
st.insert(s[i]);
child[w[i]].push_back(i);
}
for (auto it : st)
values.push_back(it);
for (int i = 1; i < n; i ++)
{
if (s[i] != s[i - 1])
all_same = false;
}
for (int j = 0; j < maxlog; j ++)
dp[j][n].ver = n;
w[n] = n;
l[n] = n;
dfs(n);
for (int i = 0; i <= n; i ++)
{
fp[0][i].ver = l[i];
fp[0][i].sum = p[i];
fp[0][i].max_strenght = s[i];
}
for (int j = 1; j < maxlog; j ++)
{
for (int i = 0; i <= n; i ++)
{
fp[j][i].ver = fp[j - 1][fp[j - 1][i].ver].ver;
fp[j][i].sum = fp[j - 1][fp[j - 1][i].ver].sum + fp[j - 1][i].sum;
fp[j][i].max_strenght = min(fp[j - 1][fp[j - 1][i].ver].max_strenght, fp[j - 1][i].max_strenght);
}
}
return;
}
long long simulate(int x, int z)
{
ll strength = z;
while(x != n)
{
///cout << x << " : " << strength << endl;
if (strength >= s[x])
{
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (dp[bit][x].max_strenght <= strength)
{
strength += dp[bit][x].sum;
x = dp[bit][x].ver;
}
}
///cout << x << endl;
}
else
{
for (int i = 0; i < (int)(values.size()); i ++)
{
if (strength >= values[i])
continue;
int new_x = x;
ll cur_strength = strength, min_strength = 1e15;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (fp[bit][new_x].ver == n)
continue;
if (cur_strength + fp[bit][new_x].sum < values[i])
{
///cout << new_x << " jump " << bit << " " << fp[bit][new_x].max_strenght << endl;
min_strength = min(min_strength, fp[bit][new_x].max_strenght);
cur_strength += fp[bit][new_x].sum;
new_x = fp[bit][x].ver;
}
}
min_strength = min(min_strength, fp[0][new_x].max_strenght);
///cout << new_x << " jump " << 0 << " " << fp[0][new_x].max_strenght << endl;
cur_strength += fp[0][new_x].sum;
new_x = fp[0][new_x].ver;
///cout << min_strength << " ----------- " << strength << endl;
if (min_strength <= strength)
{
ll to_add = 0;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
if (fp[bit][new_x].ver == n)
continue;
if (fp[bit][x].max_strenght > strength)
{
to_add += fp[bit][x].sum;
x = fp[bit][x].ver;
}
}
strength += to_add;
}
else
{
///cout << "skip " << " " << values[i] << " " << cur_strength << " " << min_strength << endl;
strength = cur_strength;
x = new_x;
}
}
}
}
return strength;
}
