#H1021. Dream and the Multiverse REMATCH

Dream and the Multiverse REMATCH

题目背景

Link

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 abstracts the fabric of spacetime as a directed rooted tree (arborescence) with NN nodes (numbered 11 through NN). Node 11 is the root and for each ii (1iN11 \le i \le N-1), the parent of node i+1i+1 is fif_i. All edges of this tree are directed away from the root.

Then, Dream employs a magical superpower and adds MM 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 ii and last event is jj. Note that i<ji \lt j does not have to hold for a plausible pair.

Dream now wants you to answer QQ queries. In each query, he gives you two positive integers ll and rr, where lrl \leq r, and he wishes to know the number of plausible pairs of events (i,j)(i,j) such that li<jrl \leq i \lt j \leq r.

输入格式

The first line of the input contains two space-separated integers NN and MM.

The second line contains N1N-1 space-separated integers f1,f2,,fN1f_1, f_2, \ldots, f_{N-1}.

MM lines follow. Each of these lines contains two space-separated integers uu and vv describing an additional edge from node uu to node vv.

The following line contains a single integer QQ.

QQ lines follow. Each of these lines contains two space-separated integers ll and rr describing a query.

输出格式

For each query, print a single line containing one integer ― the number of plausible pairs (i,j)(i,j) such that li<jrl \leq i \lt j \leq r.

输入输出样例

输入 #1

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

输出 #1

2
2
18

说明/提示

  • 2N71052 \leq N \leq 7 \cdot 10^5
  • 1Q71051 \leq Q \leq 7 \cdot 10^5
  • 0M200 \leq M \leq 20
  • 1fiN1 \le f_i \le N for each valid ii
  • 1u,vN1 \le u, v \le N
  • the graph described on the input is acyclic
  • 1lrN1 \le l \le r \le N

Subtasks

Subtask #1 (17 points): N,Q3105N,Q\le3\cdot 10^5

Subtask #2 (83 points): original constraints