Background

Problem Description

You are given a rooted tree with vertices numbered $1,2,\dots,n$. For $2\le i\le n$, $f_{i}$ is the parent of $i$. $a_1,\dots,a_n$ is a permutation of $1,\dots,n$.

There are $m$ queries. Each query gives $l,r$ and asks how many pairs $(L,R)$ satisfy $l\le L\le R\le r$, and for any $L\le a_x\le a_y\le R$, if $z$ is the lowest common ancestor of $x$ and $y$ in the tree, then $L\le a_z\le R$.

All values above are integers.

Input Format

The first line contains two integers $n\ m$.

The next line contains $n$ integers $a_1,\dots,a_n$.

The next $n-1$ lines, in order, give $f_2,\dots,f_n$.

The next $m$ lines each contain $l\ r$, describing one query.

Output Format

For each query, output one line containing the answer.

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

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

For $100\%$ of the testdata, $1\le n,m\le 2\times 10^5$, $1\le f_i\le i-1$, and $l\le r$.

For $25\%$ of the testdata, $n,m\le 100$.

For another $25\%$ of the testdata, $n,m\le 3000$.

For another $25\%$ of the testdata, $l=1,\;r=n,\;m=1$.

For another $25\%$ of the testdata, there are no special constraints.

Translated by ChatGPT 5