Dream and the Multiverse

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$ $N$ nodes (numbered $1$ $1$ through $N$ $N$ ). Node $1$ $1$ is the root and for each $i$ $i$ $(1 \le i \le N-1)$ $(1 \leq i \leq N - 1)$ , the parent of node $i+1$ $i + 1$ is $f_i$ $f_{i}$ . All edges of this tree are directed away from the root.

Then, Dream employs a magical superpower and adds $M$ $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)$ $(i, j)$ to be plausible if there is an era whose first event is $i$ $i$ and last event is $j$ $j$ .

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

Constraints

$2 \le N \le 10^5$ $2 \leq N \leq 10^{5}$

$0 \le M \le 10^5$ $0 \leq M \leq 10^{5}$

$1 \le Q \le 10^6$ $1 \leq Q \leq 10^{6}$

The given tree and $M$ $M$ extra edges form a DAG.

Subtask 1 [1%]

The tree is a line graph.

Subtask 2 [11%]

$N, M, Q \le 10^3$ $N, M, Q \leq 10^{3}$

Subtask 3 [7%]

$M \le 5$ $M \leq 5$

Subtask 4 [23%]

$N, M, Q \le 5 \times 10^4$ $N, M, Q \leq 5 \times 10^{4}$

Subtask 5 [17%]

$Q \le 10^5$ $Q \leq 10^{5}$

Subtask 6 [41%]

No additional constraints.

Input Specification

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

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

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

The following line contains a single integer $Q$ $Q$ .

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

Output Specification

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

Sample Input

Copy

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

Sample Output

Copy

6
5
27

Comments

1

Viv_CCGS commented on May 15, 2024, 12:03 p.m.

TechnobladeNeverDies, henrybaolol9. TechnobladeNeverDies

And neither does Technoblade.

-27

henrybaolol9 commented on March 25, 2022, 2:31 p.m. ← edited →

This comment is hidden due to too much negative feedback. Show it anyway.

9

CarlosJin commented on July 13, 2022, 4:06 a.m.

TechnobladeNeverDies