Dream and the Multiverse

View as PDF

Submit solution


Points: 50 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

I have gone over the scenarios in my head,

and there are 6.96969 billion outcomes, and only one of them -

- do I win.

source


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 (1 \le i \le N-1), the parent of node i+1 is f_i. All edges of this tree are directed away from the root.

Then, Dream employs a magical superpower and adds M directed edges to this tree in such a way that the resulting directed graph remains acyclic (a DAG).

Let's call a node of this DAG an event and further call a simple path on this DAG an era. Dream considers a pair of events (i, j) to be plausible if there is an era whose first event is i and last event is j.

Dream now wants you to answer Q queries. In each query, he gives you two positive integers l and r, where l \le r, and he wishes to know the number of plausible pairs of events (i, j) such that l \le i, j \le r.

Constraints

2 \le N \le 10^5

0 \le M \le 10^5

1 \le Q \le 10^6

The given tree and M extra edges form a DAG.

Subtask 1 [1%]

The tree is a line graph.

Subtask 2 [11%]

N, M, Q \le 10^3

Subtask 3 [7%]

M \le 5

Subtask 4 [23%]

N, M, Q \le 5 \times 10^4

Subtask 5 [17%]

Q \le 10^5

Subtask 6 [41%]

No additional constraints.

Input Specification

The first line of the input contains two integers N and M.

The second line contains N-1 integers f_1, f_2, \dots, f_{N-1}.

M lines follow. Each of these lines contains two integers u and v describing an additional edge from node u to node v.

The following line contains a single integer Q.

Q lines follow. Each of these lines contains two integers l and r describing a query.

Output Specification

For each query, print a single line containing one integer — the number of plausible pairs (i, j) such that l \le i, j \le r.

Sample Input

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

Sample Output

6
5
27

Comments