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 \le i \le 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 \le 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 \le i, j \le r~.

Constraints

$2 \le N \le 10^5$ ~2 \le N \le 10^5~

$0 \le M \le 10^5$ ~0 \le M \le 10^5~

$1 \le Q \le 10^6$ ~1 \le Q \le 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 \le 10^3~

Subtask 3 [7%]

$M \le 5$ ~M \le 5~

Subtask 4 [23%]

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

Subtask 5 [17%]

$Q \le 10^5$ ~Q \le 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 \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

1

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

TechnobladeNeverDies, henrybaolol9. TechnobladeNeverDies

And neither does Technoblade.

-29

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