#include "dungeons.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
using ll = long long;
const int L = 24;
int n;
vector<int> last, win;
vector<int> E[400005];
bool vis[400005];
int sz[400005], cnt;
int bound[400005];
struct hld {
int nxt[400005];
int lose[400005];
int par[400005];
void dfs_sz(int x) {
sz[x] = 1;
for (int i : E[x]) {
if (sz[i]) continue;
par[i] = x;
dfs_sz(i);
sz[x] += sz[i];
}
}
int hld_chain[400005];
int dfs_ord[400005];
int vertex[400005];
int hpath_bound[400005];
int prefix_bound[400005];
ll seg[1 << 20], dep[400005];
void dfs_hld(int x) {
vertex[dfs_ord[x] = cnt++] = x;
hpath_bound[x] = min(hpath_bound[x], bound[x]);
prefix_bound[x] = min(prefix_bound[x], bound[x]);
for (auto it = E[x].begin(); it != E[x].end(); ++it) if (sz[*it] >= sz[x]) {
E[x].erase(it);
break;
}
for (int &i : E[x]) {
if (sz[E[x][0]] < sz[i]) swap(E[x][0], i);
}
for (int i : E[x]) {
dep[i] = dep[x] + lose[i];
if (i == E[x][0]) {
hld_chain[i] = hld_chain[x];
hpath_bound[i] = max(0, hpath_bound[x] - lose[i]);
}
else {
hld_chain[i] = i;
}
prefix_bound[i] = max(0, prefix_bound[x] - lose[i]);
dfs_hld(i);
}
}
void init(int i, int s, int e) {
if (s == e) {
int v = vertex[s];
seg[i] = bound[v] + dep[v];
return;
}
int m = (s + e) / 2;
init(i + i, s, m);
init(i + i + 1, m + 1, e);
seg[i] = min(seg[i + i], seg[i + i + 1]);
}
void init() {
for (int i = 0; i <= n; ++i) E[i].clear();
memset(vis, 0, sizeof(vis));
memset(sz, 0, sizeof(sz));
memset(par, -1, sizeof(par));
memset(hpath_bound, 0x3f, sizeof(hpath_bound));
memset(prefix_bound, 0x3f, sizeof(prefix_bound));
for (int i = 0; i <= n; ++i) {
E[nxt[i]].push_back(i);
}
cnt = 0;
for (int i = 0; i <= n; ++i) {
if (sz[i]) continue;
int x = i;
while (!vis[x]) {
vis[x] = true;
x = nxt[x];
}
dfs_sz(x);
hld_chain[x] = x;
dep[x] = 0;
dfs_hld(x);
}
init(1, 0, n);
}
int find(int i, int s, int e, int y, ll v) const {
if (seg[i] > v || y < s) return -1;
if (s == e) return vertex[s];
int m = (s + e) / 2;
int r = find(i + i + 1, m + 1, e, y, v);
if (r != -1) return r;
return find(i + i, s, m, y, v);
}
void simulate_once(int &x, int &z) const {
int v = find(1, 0, n, dfs_ord[x], z + dep[x]);
// printf("[%d, %lld]\n", v, z + dep[x] - dep[v]);
z += dep[x] - dep[v] + win[v];
x = last[v];
}
void simulate(int &x, int &z) const {
// for (int i = 0; i <= n; ++i) printf("nxt[%d] = %d, lose[%d] = %d, bound[%d] = %d\n", i, nxt[i], i, lose[i], i, bound[i]);
// printf("[%d, %d] -> ", x, z);
while (true) {
if (hpath_bound[x] <= z) {
simulate_once(x, z);
return;
}
int p = par[hld_chain[x]];
if (p == -1) {
z += dep[x];
x = hld_chain[x];
break;
}
z += dep[x] - dep[p];
x = p;
// printf("[%d, %d] -> ", x, z);
}
int rt = lose[x];
z += rt;
x = nxt[x];
// printf("[%d, %d] -> ", x, z);
if (prefix_bound[x] > z) {
int add = dep[x] + rt;
z += ((prefix_bound[x] - z - 1) / add + 1) * add;
// printf("[%d, %d] -> ", x, z);
}
while (true) {
if (hpath_bound[x] <= z) {
simulate_once(x, z);
return;
}
int p = par[hld_chain[x]];
if (p == -1) exit(1);
z += dep[x] - dep[p];
x = p;
// printf("[%d, %d] -> ", x, z);
}
exit(2);
}
} sub[L];
ll win_all[400005];
const int inf = 1e8;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
::n = n;
::win = s;
::win.push_back(0);
::last = w;
::last.push_back(n);
win_all[n] = 0;
for (int i = n; i--; ) win_all[i] = win_all[w[i]] + s[i];
for (int i = 0; i < L; ++i) {
int d = 1 << i;
for (int j = 0; j < n; ++j) {
if (s[j] <= d) {
sub[i].nxt[j] = w[j];
sub[i].lose[j] = s[j];
bound[j] = inf;
}
else {
sub[i].nxt[j] = l[j];
sub[i].lose[j] = p[j];
bound[j] = s[j];
}
sub[i].nxt[n] = n;
sub[i].lose[n] = 0;
bound[n] = 0;
}
sub[i].init();
}
return;
}
long long simulate(int x, int z) {
for (int i = 0; i < L; ++i) if (x < n && (1 << i) <= z && z < (1 << (i + 1))) sub[i].simulate(x, z);
return z + win_all[x];
}
