P7331 Dream and the Multiverse REMATCH

[Link](https://youtu.be/tylNqtyj0gs?t=2388) *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 将时空的结构抽象为一个有 $N$ 个节点（编号为 $1$ 到 $N$）的有向根树（树形结构）。节点 $1$ 是根节点，对于每个 $i$（$1 \le i \le N-1$），节点 $i+1$ 的父节点是 $f_i$。这棵树的所有边都是从根节点指向外部的。 然后，Dream 使用一种神奇的超能力，向这棵树中添加了 $M$ 条有向边，使得结果图仍然是无环的（有向无环图，DAG）。 我们称这个 DAG 的一个节点为一个*事件*，并进一步称这个 DAG 上的一条简单路径为一个*时代*。Dream 认为一对事件 $(i,j)$ 是*可能的*，如果存在一个时代，其第一个事件是 $i$，最后一个事件是 $j$。注意，对于一个可能的对，$i < j$ 并不一定成立。 Dream 现在希望你回答 $Q$ 个查询。在每个查询中，他给你两个正整数 $l$ 和 $r$，其中 $l \leq r$，他希望知道有多少对可能的事件 $(i,j)$ 满足 $l \leq i < j \leq r$。

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。 第二行包含 $N-1$ 个空格分隔的整数 $f_1, f_2, \ldots, f_{N-1}$。 接下来的 $M$ 行中，每行包含两个空格分隔的整数 $u$ 和 $v$，描述了一条从节点 $u$ 到节点 $v$ 的额外边。 接下来的行包含一个整数 $Q$。 接下来的 $Q$ 行中，每行包含两个空格分隔的整数 $l$ 和 $r$，描述了一个查询。

对于每个查询，输出一行，包含一个整数——满足 $l \leq i < j \leq r$ 的可能事件对 $(i,j)$ 的数量。

- $2 \leq N \leq 7 \cdot 10^5$ - $1 \leq Q \leq 7 \cdot 10^5$ - $0 \leq M \leq 20$ - 对于每个有效的 $i$，$1 \le f_i \le N$ - $1 \le u, v \le N$ - 输入描述的图是无环的 - $1 \le l \le r \le N$ ### 子任务 **子任务 #1 (17 分):** $N,Q \le 3 \cdot 10^5$ **子任务 #2 (83 分):** 原始约束条件。 题面翻译由 ChatGPT-4o 提供。