#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400010;
const int LG = 25;
int up[N][LG];
ll sum[N][LG];
int dp[N];
int S;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
S = s[0];
dp[n] = 0;
for (int i = n - 1; i >= 0; i--) dp[i] = dp[w[i]] + 1;
up[n][0] = n;
sum[n][0] = 0;
for (int i = 0; i < n; i++){
up[i][0] = l[i];
sum[i][0] = p[i];
}
for (int j = 1; j < LG; j++){
for (int i = 0; i <= n; i++){
int x = up[i][j - 1];
up[i][j] = up[x][j - 1];
sum[i][j] = sum[i][j - 1] + sum[x][j - 1];
}
}
return;
}
pair<int, ll> ancestor(int x, int k){
ll res = 0;
for (int i = LG - 1; i >= 0; i--){
if (k & (1 << i)){
res += sum[x][i];
x = up[x][i];
}
}
return make_pair(x, res);
}
long long simulate(int x, int z) {
if (z >= S) return z + (ll)dp[x] * S;
int l = 0, r = 2e7;
while (l <= r){
int m = (l + r) >> 1;
pair<int, ll> res = ancestor(x, m);
if (z + res.second >= S){
r = m - 1;
} else {
l = m + 1;
}
}
r++;
pair<int, ll> res = ancestor(x, r);
return z + res.second + (ll)dp[res.first] * S;
}
