P8528 [Ynoi2003] Suzuhara Lulu


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.

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.

For each query, output one line containing the answer.

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