题目链接：https://uoj.ac/contest/82/problem/806

看到赛时过的人很多都写的是倍增，之前没懂但现在懂了的我来解释一下算法的原理：

首先需要感性理解出一个事实：

设 $f(i,j)$ 为 $i$ 过了 $j$ 时间后的 $a$，则 $f(i,j)=\min(a_i+j,\max(a_i,f(fa_i,j-1)+1))$

感性理解完后，再来写出

$$f(fa_i,j-1)=\min(a_{fa_i}+j-1,\max(a_{fa_i},f(fa_{fa_i},j-2)+1))$$

把两式合并，得到

$$f(i,j)=\min(a_i+j,a_{fa_i}+j,\max(a_i,a_{fa_i}+1,f(fa_{fa_i},j-2)+2))$$

从此可窥见端倪：上式中的 $1$ 代表 $2^{j-1}$，$2$ 代表 $2^j$，可以用倍增维护。

用倍增维护 min(... 和 max(... 即可。其中由于上界（min(...）只和查询的总时间 $d$ 有关，所以预处理时不用预处理 +j。而最后一项，是 $g$ 跳 $d$ 步的终点的 $a$ + $d$。

一个细节需要注意！

对于两个区间 $[l1,r1],[l2,r2] (l1\le r1\le l2\le r2)$，依次进行复合后会变成一个长度为负数的区间，从而复合映射时会出错（你可以手动试试看）。

解决办法是，如果从后往前（由于 dp 顺序，肯定是更接近 $i$ 的更后复合）复合到某个区间时出现了这种情况，我们就要在这种情况发生的前一个点处停止。而更前面的区间是可以完全被忽略的，这可以感性理解。

因此还需要注意不能用 $g$ 条 $d$ 步的终点的 $a$ + $d$ 作为最后一项，而要用实际跳到的点作为终点，用它的 $a$ + $s$。其中 $s$ 为实际跳的步数。

int main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)p[i]=read();
    for(int i=1;i<=n;i++){
        fa[0][i]=p[i];
        L[0][i]=R[0][i]=a[i];
    }
    for(int j=1;j<=17;j++)
        for(int i=1;i<=n;i++){
            fa[j][i]=fa[j-1][fa[j-1][i]];
            L[j][i]=max(L[j-1][i],L[j-1][fa[j-1][i]]+(1<<j-1));
            R[j][i]=min(R[j-1][i],R[j-1][fa[j-1][i]]);
        }
    for(int i=1;i<=q;i++){
        k=read(),t=read();
        int l=0,r=2e9,s=0,pp=k;
        for(int j=17;j>=0;j--)
            if(s+(1<<j)<=t)if(max(l,L[j][k]+s)<=min(r,R[j][k]+t)){
                l=max(l,L[j][k]+s),r=min(r,R[j][k]+t);
                k=fa[j][k],s+=(1<<j);
            }
        cout<<min(max(a[k]+s,l),r)<<'\n';
    }
    return 0;
}