欢乐游戏鸡

要解决此题，有很多简单的方法，也有很多不简单的方法，也有很多非常复杂的方法。

这里介绍两种方法，一种简单，一种非常复杂。

题意

给定一棵树，你只能从一个节点向其子节点行动。有多次游戏，每次游戏你将出生在 $s$，前往 $t$，如果遇到一个等级高于你的节点，你会死亡，回到 $s$，同时等级加 $1$。你不一定要沿着 $s-t$之间的最短路前进，则最少多少次移动可以到达 $t$？移动指经过一条边，且每次游戏不考虑 $s,t$两点的等级。

分析

首先，我们引入一个概念：练级。

这是一个在小学生的口中经常听到的词语，但是它体现了这道题的精髓所在。练级是指通过刷野怪达到更高的等级，去挑战 boss。

在本题中，为了通过 $s-t$路径上等级最高的节点，你必须在 $s$附近练级，使等级达到该节点的等级，方可通过该节点。

现在的问题就是：如何高效地练级？

每次重生，我们找到离自己最近的，等级比自己高的野怪，然后去挑战它。然后我们会死，但是死得值得。因为这个野怪是你提高等级最高效的途径。可以证明这样练级是最优的。

如果我们把每个野怪抽象成一个二维平面上的点，其横坐标是等级，纵坐标是到出生点的距离，那么，我们用来练级的野怪将会是所有点最下方的几个点，并且从左到右这些点纵坐标单调递增。而达到 $x$级所花的时间将是几个举行的面积的和。这个画画图不难理解。

由于用来练级的野怪只能是子树中的野怪，并且，以某个节点为根，用来练级的野怪，一定是其所有子树用来练级的野怪的子集。因此我们不妨考虑合并子树信息。

有两种办法合并子树信息：

Splay

由于我们需要维护一个单调的序列，我们不妨考虑平衡树。在树上，平衡树的启发式合并复杂度是 $O(n\log n)$的。（并不是 $O(n\log^2n)$，可以用 $finger-search$相关理论证明）。因此这道题的复杂度也是 $O(n\log n)$的。

剩下的就不难了，主要难在实现。我实现了一个下午，300 多行，实在不想写下去，因此放弃了这种做法。

线性表

与深度有关的 Dp 信息的维护往往可以用长短链剖分优化成 $O(n)$。具体可以见 BZOJ4543。这道题我们要在树上合并的序列就与深度有关。

我们知道，用于练级的野怪序列 ${(w_i,d_i)}$一定满足 $\forall i<j,\ w_i<w_j,\ d_i<d_j$。因此，序列长度一定是 $O(dep)$的。其中 $dep$是子树深度。并且，由于我们只需要将两个序列 $d$重合的部分进行合并，剩下的部分保留，合并两个序列的复杂度是 $O(min(n_1,n_2))$的，因此，如果我们每次先递归最深的子树，将其余子树的序列合并到最深的子树信息内，合并的总复杂度是 $O(n)$的。

为什么呢？合并子树信息的操作可以看成：每一次，一条短的链被’pia’ 地一声贴在了一条比它长的链上，然后这条长的链的信息就是两者信息的综合。贴一次复杂度是 $O(len)$的，并且全部链的总长度减少了 $\Omega(len)$，所以总时间复杂度是 $O(\sum len) = O(n)$ 的。

但是，我们还需要求 “达到一定等级的用时”，这相当于是求一段东西的前缀和，因此，我们不妨在合并两条链的时候顺便维护以下前缀和就行了。

具体的实现有一些细节，比如：为了方便，每一条链的信息都要按 dfs 序存在一个数组里，且合并的两条链一定是数组内相邻的，这样，合并出来的新链将可以占用合并前两条链的空间 (实际上只占用较长链的空间)。还比如，合并两条链需要用到类似于归并的过程，在归并过程中各种边界条件的特判需要注意。

下面给出线性表的代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define MX 300003
#define wi first
#define di second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int N, M, W[MX];
vector<pii> qur[MX];

template <typename T> void read(T& x)
{
    x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x*10+c-'0', c = getchar();
}

struct GRAPH
{
    int fst[MX], nxt[MX], v[MX], lnum;
    int fa[MX][20], mx[MX][20];
    int dep[MX], len[MX], son[MX];

    void addeg(int nu, int nv)
    {
        nxt[++lnum] = fst[nu];
        fst[nu] = lnum;
        v[lnum] = nv;
    }

    void dfs(int x, int f, int d)
    {
        dep[x] = d;
        fa[x][0] = f;
        mx[x][0] = W[f];
        for(int i=fst[x]; i; i=nxt[i])
        {
            dfs(v[i], x, d+1);
            len[x] = max(len[x], len[v[i]]);
            if(!son[x] || len[v[i]]>len[son[x]]) son[x] = v[i];
        }
        len[x]++;
    }

    void init()
    {
        dfs(1, 0, 1);
        for(int j=1; j<20; j++)
            for(int i=1; i<=N; i++)
                mx[i][j] = max(mx[i][j-1], mx[fa[i][j-1]][j-1]),
                fa[i][j] = fa[fa[i][j-1]][j-1];
    }

    int jump(int x, int d)
    {
        int ret = 0;
        for(int i=19; i>=0; i--)
            if(dep[fa[x][i]] >= d)
                ret = max(ret, mx[x][i]),
                x = fa[x][i];
        return ret;
    }
} G;

void input()
{
    int a, b;
    read(N);
    for(int i=1; i<=N; i++) read(W[i]);
    for(int i=1; i<N; i++)
    {
        read(a);
        G.addeg(a, i+1);
    }
    read(M);
    for(int i=1; i<=M; i++)
    {
        scanf("%d%d", &a, &b);
        qur[a].push_back(make_pair(b, i));
    }
}

pii f[MX];
ll s[MX],ans[MX];
int lft[MX], rgt[MX];
int dfn[MX], dfc;

void insert(int tar, const pii& nod)    //nod.di can't be greater than f[lft[tar]].di
{
    while(lft[tar]<=rgt[tar] && f[lft[tar]].wi<=nod.wi) lft[tar]++;
    if(lft[tar]>rgt[tar] || f[lft[tar]].di!=nod.di)
    {
        f[--lft[tar]] = nod;
        int p = lft[tar];
        s[p] = s[p+1] + 1ll*(f[p+1].wi-f[p].wi)*f[p+1].di;
    }
}

void merge(int tar, int src)
{
    static pii tmp[MX];
    int t = 0;
    while(lft[tar]<=rgt[tar] && f[lft[tar]].di < f[rgt[src]].di) tmp[++t] = f[lft[tar]++];
    while(t && lft[src]<=rgt[src])
    {
        if(tmp[t].di > f[rgt[src]].di) insert(tar, tmp[t--]);
        else insert(tar, f[rgt[src]--]);
    }
    while(t) insert(tar, tmp[t--]);
    while(lft[src]<=rgt[src]) insert(tar, f[rgt[src]--]);
}

ll query(int x, int w, int d)
{
    int p = lower_bound(f+lft[x], f+rgt[x]+1, make_pair(w, 0)) - f;
    if(p == lft[x])
    {
        ll retr = 1ll * w * f[p].di;
        return retr - 1ll * w * d;
    }
    else
    {
        ll retl = s[lft[x]] - s[p-1] + 1ll * f[lft[x]].wi * f[lft[x]].di;
        ll retr = 1ll * (w-f[p-1].wi) * f[p].di;
        return (retl + retr) - 1ll * w * d;
    }
}

void dfs(int x)
{
    dfn[x] = ++dfc;
    if(G.son[x])
    {
        dfs(G.son[x]);
        lft[x] = lft[G.son[x]];
        rgt[x] = rgt[G.son[x]];
    }
    else lft[x] = dfn[x]+1, rgt[x] = dfn[x];
    for(int i=G.fst[x]; i; i=G.nxt[i])
        if(G.v[i] != G.son[x])
            dfs(G.v[i]), merge(x, G.v[i]);
    for(auto it=qur[x].begin(); it!=qur[x].end(); it++)
        ans[it->second] = query(x, G.jump(it->first, G.dep[x]+1), G.dep[x]) + G.dep[it->first] - G.dep[x];
    insert(x, make_pair(W[x], G.dep[x]));
}

int main()
{
    input();
    G.init();
    dfs(1);
    for(int i=1; i<=M; i++) printf("%lld\n", ans[i]);
    return 0;
}