#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 400005;
const int m = 28;
const ll INF = 1000000009000000009;
int n;
vector<int> S, P, W, L;
vector<int> t[N];
ll st[m][N];
int ut[m][N];
void dfst(int x, int j)
{
if (x == n || S[x] >= (1 << j))
{
st[j][x] = 0;
ut[j][x] = x;
}
for (int i = 0; i < sz(t[x]); ++i)
{
int h = t[x][i];
ut[j][h] = ut[j][x];
st[j][h] = st[j][x] + S[h];
dfst(h, j);
}
}
pair<int, ll> u[m][N];
//////////////////////////////////////////////////////////////
vector<vector<int> > vv;
int c[N];
bool dfsc(int x, int j)
{
c[x] = 1;
int h = u[j][x].fi;
if (!c[h])
{
if (dfsc(h, j))
{
c[x] = 2;
return true;
}
}
else if (c[h] == 1)
{
vector<int> v;
while (h != x)
{
v.push_back(h);
h = u[j][h].fi;
}
v.push_back(x);
vv.push_back(v);
c[x] = 2;
return true;
}
c[x] = 2;
return false;
}
int minc[m][N];
ll sc[m][N];
vector<pair<int, ll> > g[N];
int q[N];
ll d[m][N];
void dfs0(int x, int j)
{
q[x] = 1;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
d[j][h] = d[j][x] + g[x][i].se;
dfs0(h, j);
q[x] += q[h];
}
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (q[h] > q[g[x][0].fi])
{
swap(g[x][i], g[x][0]);
}
}
}
int tin[m][N], tout[m][N], ti[m], rtin[m][N];
int f[m][N];
int p0[m][N];
ll minf[m][N];
void dfs1(int x, int j)
{
tin[j][x] = ++ti[j];
rtin[j][tin[j][x]] = x;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
p0[j][h] = x;
if (i == 0)
{
f[j][h] = f[j][x];
minf[j][h] = minf[j][x];
minf[j][h] = min(minf[j][h], d[j][h] + S[h]);
}
else
{
f[j][h] = h;
minf[j][h] = d[j][h] + S[h];
}
dfs1(h, j);
}
tout[j][x] = ti[j];
}
ll minu[m][N * 4];
ll bu[N];
void bil(int j, int tl, int tr, int pos)
{
if (tl == tr)
{
minu[j][pos] = bu[tl];
return;
}
int m = (tl + tr) / 2;
bil(j, tl, m, pos * 2);
bil(j, m + 1, tr, pos * 2 + 1);
minu[j][pos] = min(minu[j][pos * 2], minu[j][pos * 2 + 1]);
}
void ubd(int j, int tl, int tr, int x, ll y, int pos)
{
if (tl == tr)
{
minu[j][pos] = y;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(j, tl, m, x, y, pos * 2);
else
ubd(j, m + 1, tr, x, y, pos * 2 + 1);
minu[j][pos] = min(minu[j][pos * 2], minu[j][pos * 2 + 1]);
}
int qry(int j, int tl, int tr, int l, int r, ll y, int pos)
{
if (l > r)
return ti[j] + 1;
if (tl == l && tr == r)
{
if (minu[j][pos] > y)
return ti[j] + 1;
if (tl == tr)
return tl;
}
int m = (tl + tr) / 2;
int ans = qry(j, m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
if (ans <= ti[j])
return ans;
return qry(j, tl, m, l, min(m, r), y, pos * 2);
}
int qry(int j, int x, ll y)
{
int qq = 0;
while (1)
{
++qq;
assert(qq <= 20);
if (minf[j][x] <= y)
{
int ans = qry(j, 1, ti[j], tin[j][f[j][x]], tin[j][x], y, 1);
assert(ans <= ti[j]);
return rtin[j][ans];
}
x = f[j][x];
if (d[j][x] == 0)
return x;
x = p0[j][x];
}
}
void init(int NN, std::vector<int> SS, std::vector<int> PP, std::vector<int> WW, std::vector<int> LL) {
n = NN;
S = SS;
P = PP;
W = WW;
L = LL;
for (int i = 0; i < n; ++i)
{
t[W[i]].push_back(i);
}
for (int j = 0; j < m; ++j)
{
vv.clear();
for (int i = 0; i <= n; ++i)
{
g[i].clear();
c[i] = 0;
}
dfst(n, j);
for (int x = 0; x < n; ++x)
{
if (S[x] >= (1 << j))
{
u[j][x] = m_p(ut[j][L[x]], P[x] + st[j][L[x]]);
}
}
u[j][n] = m_p(n, 0);
////////////////////////////////////////////////////////////////////////////
for (int x = 0; x <= n; ++x)
{
if (x == n || S[x] >= (1 << j))
{
if (!c[x])
{
dfsc(x, j);
}
}
}
for (int x = 0; x <= n; ++x)
{
c[x] = 0;
}
for (int i = 0; i < sz(vv); ++i)
{
c[vv[i][0]] = 1;
if (vv[i][0] == n)
{
assert(sz(vv[i]) == 1);
continue;
}
minc[j][vv[i][0]] = S[vv[i][0]];
for (int k = 0; k < sz(vv[i]); ++k)
{
minc[j][vv[i][0]] = min(minc[j][vv[i][0]], S[vv[i][k]]);
sc[j][vv[i][0]] += u[j][vv[i][k]].se;
}
}
for (int x = 0; x <= n; ++x)
{
if (x == n || S[x] >= (1 << j))
{
if (!c[x])
g[u[j][x].fi].push_back(m_p(x, u[j][x].se));
}
}
for (int x = 0; x <= n; ++x)
{
if (c[x])
{
dfs0(x, j);
f[j][x] = x;
if (x < n)
minf[j][x] = S[x];
dfs1(x, j);
}
}
for (int x = 0; x <= n; ++x)
{
if (x == n || S[x] >= (1 << j))
{
if (x != n)
bu[tin[j][x]] = d[j][x] + S[x];
//ubd(j, 1, ti[j], tin[j][x], d[j][x] + S[x], 1);
else
{
assert(d[j][x] == 0);
bu[tin[j][x]] = d[j][x];
//ubd(j, 1, ti[j], tin[j][x], d[j][x], 1);
}
}
}
bil(j, 1, ti[j], 1);
}
}
long long simulate(int x, int Z) {
ll z = Z;
int qq = 0;
while (x != n)
{
for (int j = m - 1; j >= 0; --j)
{
if (z >= (1 << j))
{
z += st[j][x];
x = ut[j][x];
/*while (x != n && z < S[x])
{
z += u[j][x].se;
x = u[j][x].fi;
}*/
while (x != n && z < S[x])
{
++qq;
int p = qry(j, x, z + d[j][x]);
z += d[j][x] - d[j][p];
x = p;
if (x != n && z < S[x])
{
ll q = (minc[j][x] - z);
if (q < 0)
q = 0;
else
q = (q / sc[j][x]);
z += q * sc[j][x];
if (z < S[x])
{
z += u[j][x].se;
x = u[j][x].fi;
}
}
}
if (x != n)
{
assert(z >= S[x]);
z += S[x];
x = W[x];
}
break;
}
}
}
assert(qq <= m * 3);
return z;
}
/*
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
*/
