题目背景

题目描述

给定一棵有根树，顶点编号为 $1,2,\dots,n$，对 $2\le i\le n$ 有 $f_{i}$ 为 $i$ 的父亲。$a_1,\dots,a_n$ 是 $1,\dots,n$ 的排列。

共 $m$ 次询问，每次询问给出 $l,r$，询问有多少个二元组 $L,R$，满足 $l\le L\le R\le r$，且对任意 $L\le a_x\le a_y\le R$，有 $x,y$ 在树上的最近公共祖先 $z$ 满足 $L\le a_z\le R$。

以上所有数值为整数。

输入格式

第一行两个整数 $n\ m$；

接下来一行，$n$ 个整数 $a_1,\dots,a_n$；

接下来 $n-1$ 行，依次为 $f_2,\dots,f_n$；

接下来 $m$ 行，每行 $l\ r$ 表示一个询问。

输出格式

对每个询问，输出一行，表示答案。

5 5
2 5 1 3 4
1
2
3
4
1 1
1 4
3 3
2 2
1 1

1
10
1
1
1

提示

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $1\le n,m\le 2\times 10^5$，$1\le f_i\le i-1$，$l\le r$。

对于 $25\%$ 的数据，满足 $n,m\le 100$。

对于另外 $25\%$ 的数据，满足 $n,m\le 3000$。

对于另外 $25\%$ 的数据，满足 $l=1,\;r=n,\;m=1$。

对于另外 $25\%$ 的数据，无特殊限制。