P7349 "MCOI-04" Dream and the Multiverse

[Link](https://youtu.be/tylNqtyj0gs?t=2388) *I have gone over the scenarios in my head,* *and there are 6.96969 billion outcomes, and only one of them -* *- do I win.*

Dream models time and space as a rooted directed tree with $n$ nodes, where the root is node $1$ and all edges are directed from shallow to deep. Dream uses his superpower to add $m$ extra directed edges to this tree, and the final graph is still a directed acyclic graph. Dream further models an event as a node in the graph, and models an era as a simple path in the graph. Dream considers a pair of events $(i,j)$ to be **feasible** if and only if there exists an era whose first event is $i$ and last event is $j$. Dream now 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 **feasible** event pairs $(i,j)$ satisfy $i,j \in [l,r]$.

The first line contains two integers $n,m$. The next line contains $n-1$ positive integers describing the tree. The $i$-th number denotes the index of the parent of node $i+1$, namely $f_i$, which means there is a directed edge from $f_i$ to $i+1$. The next $m$ lines each contain two positive integers $u,v$, indicating an extra directed edge added from $u$ to $v$. The next line contains a positive integer $q$. The next $q$ lines each contain two positive integers $l,r$, representing a query.

Output $q$ lines, each containing one integer, which is the answer to the corresponding query.

#### Constraints and Notes **This problem uses bundled testdata.** - Subtask 1 (1 pts): The tree is a chain. - Subtask 2 (11 pts): $n,q,m \le 1000$. - Subtask 3 (7 pts): $m \le 5$. - Subtask 4 (23 pts): $n,q,m \le 5 \times 10^4$. - Subtask 5 (17 pts): $q \le 10^5$. - Subtask 6 (41 pts): No special constraints. For $100\%$ of the testdata, $2 \le n \le 10^5$, $0 \le m \le 10^5$, $1 \le q \le 10^6$. It is **guaranteed** that the extra edges will not form a cycle, and the given $f_i$ form a rooted tree with root $1$. It is **guaranteed** that $l \le r$. #### Notes [Minecraft OI Round 4](https://www.luogu.com.cn/contest/33344) C idea & solution: w33z8kqrqk8zzzx33 check: ClCN Translated by ChatGPT 5