一番战斗之后，程序猿被计算鸡们赶走了。随着垫子计算鸡一声令下：“追！”，于是计算鸡村全村上下开始乘胜追击。计算鸡们希望在新的一年到来之际给程序猿以重创，出掉这一年的恶气。
可是程序猿一追就走，一走就跑，一跑就无影无踪。计算鸡们开始跋山涉水寻找程序猿的踪迹。快乐游戏鸡跟随大部队走着走着，突然说道：“我好像打过类似的游戏”。
快乐游戏鸡玩过的游戏是这样的：给定一棵 $n$ 个结点的树，其中 $1$ 号结点是根。每次玩家可以在树上行走，走过一条边需要 $1$ 秒的时间，但只能往当前所在的点的某个儿子走，不能往父亲走。每次游戏需要从 $s$ 号结点走到 $t$ 号结点去。
玩家有一个总死亡次数，初始为 $0$。每个结点上有一个程序猿和一个参数 $w_i$，如果走到结点 $i$ 的时候，当前总的死亡次数小于 $w_i$，那么玩家就会立刻死亡并回到起点 $s$，且该死亡过程不需要时间；如果总死亡次数大于等于 $w_i$，那么玩家就能熟练地对付程序猿从而安然无恙。注意每次游戏时不需要考虑 $s$ 和 $t$ 上的程序猿。
该游戏会进行若干轮，每轮会清空总死亡次数并给出一组新的 $s, t$。现在请你对于每一轮游戏输出走到 $t$ 所需要的最短时间（单位为秒）。
保证每个询问的 $s$ 可以到达 $t$。
首先考虑怎么走最优，设当前死亡次数为(x),刚开始为(0)，先找到一个最近的点满足(w_i>x)，然后死够了再找下一个(w_i)，直到(x)刚好等于这条链的最大值(max(w_i))
那么我们可以对每个点按深度维护一个单调栈，对一个询问先二分死的次数在单调栈里的位置，然后计算贡献
计算完这个点的贡献直接向上合并单调栈，我们可以用长链剖分按dfs序分配空间
所以总复杂度是(O(nlogn))
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
const int N = 3e5;
const int lg = 20;
using namespace std;
int len[N + 5],n,Q,w[N + 5],edge[N + 5],nxt[N + 5],head[N + 5],edge_cnt,fa[N + 5][lg + 1],mx[N + 5][lg + 1],dfn[N + 5],dep[N + 5],son[N + 5],L[N + 5],R[N + 5],dfn_cnt,cnt;
long long ans[N + 5],sm[N + 5];
struct Query
{
int y,id;
};
struct stack
{
int dep,w;
}stk[N + 5],q[N + 5];
vector <Query> d[N + 5];
void add_edge(int u,int v)
{
edge[++edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void dfs1(int u)
{
mx[u][0] = w[fa[u][0]];
for (int i = 1;i <= lg;i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1],mx[u][i] = max(mx[u][i - 1],mx[fa[u][i - 1]][i - 1]);
dep[u] = dep[fa[u][0]] + 1;
for (int i = head[u];i;i = nxt[i])
{
int v = edge[i];
dfs1(v);
if (len[v] > len[son[u]])
son[u] = v;
}
len[u] = len[son[u]] + 1;
}
int Lca(int x,int y)
{
int ans = 0;
for (int i = lg;i >= 0;i--)
if (dep[fa[x][i]] > dep[y])
ans = max(ans,mx[x][i]),x = fa[x][i];
return ans;
}
void add(int x,stack a)
{
while (L[x] <= R[x] && stk[L[x]].w <= a.w)
L[x]++;
if (L[x] > R[x])
sm[--L[x]] = 0,stk[L[x]] = a;
else
if (stk[L[x]].dep > a.dep)
stk[--L[x]] = a,sm[L[x]] = sm[L[x] + 1] + 1ll * stk[L[x] + 1].dep * (stk[L[x] + 1].w - a.w);
}
void merge(int x,int y)
{
cnt = 0;
while (L[x] <= R[x] && stk[L[x]].dep <= stk[R[y]].dep)
q[++cnt] = stk[L[x]++];
while (cnt && L[y] <= R[y])
if (q[cnt].dep >= stk[R[y]].dep)
add(x,q[cnt--]);
else
add(x,stk[R[y]--]);
while (cnt)
add(x,q[cnt--]);
while (L[y] <= R[y])
add(x,stk[R[y]--]);
}
long long query(int u,int v)
{
int ma = Lca(v,u),l = L[u],r = R[u],mid;
while (l <= r)
{
mid = l + r >> 1;
if (stk[mid].w < ma)
l = mid + 1;
else
r = mid - 1;
}
if (stk[L[u]].w <= ma)
return 1ll * sm[L[u]] - 1ll * sm[l] + 1ll * stk[L[u]].dep * stk[L[u]].w - 1ll * dep[u] * ma - 1ll * (stk[l].w - ma) * stk[l].dep;
else
return 1ll * ma * (stk[l].dep - dep[u]);
}
void dfs2(int u)
{
dfn[u] = ++dfn_cnt;
if (son[u])
dfs2(son[u]),L[u] = L[son[u]],R[u] = R[son[u]];
else
L[u] = dfn_cnt,R[u] = dfn_cnt - 1;
for (int i = head[u];i;i = nxt[i])
{
int v = edge[i];
if (v == son[u])
continue;
dfs2(v);
merge(u,v);
}
vector <Query>::iterator it;
for (it = d[u].begin();it != d[u].end();it++)
{
int v = it -> y,id = it -> id;
ans[id] = query(u,v) + dep[v] - dep[u];
}
add(u,(stack){dep[u],w[u]});
}
int main()
{
//freopen("ex.in","r",stdin);
//freopen("ex.out","w",stdout);
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%d",&w[i]);
int u,v;
for (int i = 2;i <= n;i++)
{
scanf("%d",&fa[i][0]);
add_edge(fa[i][0],i);
}
dfs1(1);
scanf("%d",&Q);
for (int i = 1;i <= Q;i++)
{
scanf("%d%d",&u,&v);
d[u].push_back((Query){v,i});
}
dfs2(1);
for (int i = 1;i <= Q;i++)
printf("%lld
",ans[i]);
return 0;
}