409405: GYM103500 D multiverse FINALE

Dream abstracts the fabric of spacetime as a directed rooted tree (arborescence) with $$$n$$$ nodes (numbered $$$1$$$ through $$$n$$$). Node $$$1$$$ is the root and for each $$$i$$$ from $$$2$$$ to $$$n$$$, the parent of node $$$i$$$ is $$$f_i$$$. All edges of this tree are directed away from the root; let this graph be $$$T$$$.

Consider $$$m$$$ additional directed edges $$$(u_1,v_1),(u_2,v_2),\dots,(u_m,v_m)$$$; let this graph be $$$E$$$. $$$T\cup U$$$ is a directed acyclic graph.

Dream considers a pair of nodes $$$(i,j)$$$ to be plausible with respect to a graph $$$G$$$ if there is a path in $$$G$$$ from $$$i$$$ to $$$j$$$. Let $$$f(G,l,r)$$$ where $$$1\le l\le r\le n$$$ be the number of pairs $$$(i,j)$$$ such that $$$l\le i<j\le r$$$ and $$$(i,j)$$$ is plausible with respect to $$$G$$$.

Dream now wants you to answer $$$q$$$ queries of the following form: for two integers $$$l,r$$$ where $$$1\le l\le r\le n$$$, find $$$f(T\cup U,l,r)-f(T,l,r)$$$.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n\le 7\times 10^5$$$, $$$0\le m\le 100$$$).

The second line contains $$$n-1$$$ integers $$$f_2,f_3,\dots,f_n$$$, indicating that there is an edge from $$$f_i$$$ to $$$i$$$. The test data guarantees that this forms an arborescence.

The $$$i$$$-th of the next $$$m$$$ lines contain two integers $$$u_i$$$ and $$$v_i$$$, describing an additional edge. The test data guarantees $$$T\cup U$$$ is a DAG.

The next line contains an integer $$$q$$$ ($$$1\le q\le 3\times 10^5$$$).

The next $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$, describing a query.

For each query, output on one line the answer to that query.

• In the first subtask, worth $$$3$$$ points, $$$n,q\le 1000$$$.
• In the second subtask, worth $$$29$$$ points, $$$n,q\le 2\times 10^5$$$ and $$$m\le 50$$$.
• In the third subtask, worth $$$31$$$ points, $$$m\le 50$$$.
• In the final subtask, worth $$$37$$$ points, no additional constraints are posed.

2 2
1
1 2
1 2
1
1 2

0

8 2
1 2 5 1 4 3 3
2 4
4 7
3
4 6
5 7
1 8

0
1
4