P7570 "MCOI-05" Duoyu.

Dream abstracts space-time as a rooted directed tree with $n$ nodes. The root is node $1$, and all edges are directed from shallow to deep (from ancestor to descendant). Dream uses his superpower to add $m$ additional directed edges to this tree, but the final graph is still a directed acyclic graph (DAG). Dream further abstracts an event as a node in the graph, and an era as a simple path in the graph. Dream says that a pair of events $(i, j)$ is **feasible** if and only if there exists an era such that the first event of the era is $i$ and the last event is $j$. Dream is not satisfied with counting ordinary feasible pairs. He believes the additional edges added by the superpower are very important. Dream says that a pair of events $(i, j)$ is **conditionally feasible** if and only if $(i, j)$ is feasible, and after removing all additional edges, $(i, j)$ becomes infeasible. Now Dream has $q$ queries. The $i$-th query is given by two positive integers $l_i$ and $r_i$, where $l_i \le r_i$. For each query, Dream wants to know how many **conditionally feasible** event pairs $(i, j)$ satisfy $l \le i < j \le r$.

The first line contains two integers $n, m$. The next line contains $n - 1$ positive integers describing the tree structure. The $i$-th number denotes the index of the parent of node $i + 1$, $f_i$. That is, there is an edge from $f_i$ to $i + 1$. The next $m$ lines each contain two positive integers $u, v$, denoting an additional edge directed from $u$ to $v$. The next line contains a positive integer $q$. The next $q$ lines each contain two positive integers $l, r$, denoting one query.

Output $q$ lines. Each line contains one integer, the answer to the corresponding query.

- Subtask 1 (3 pts): $n, q \le 1000$, 3s. - Subtask 2 (29 pts): $n, q \le 2 \times 10^5$, $m \le 50$, 3s. - Subtask 3 (31 pts): $m \le 50$, 5s. - Subtask 4 (37 pts): no extra constraints, 5s. For $100\%$ of the testdata, $2 \le n \le 7 \times 10^5$, $1 \le q \le 3 \times 10^5$, $0 \le m \le 100$. Translated by ChatGPT 5