「MCOI-04」Dream and the Multiverse

[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$ 并且所有边的方向都为浅往深。 Dream 用他的超能力在这颗树上额外添加 $m$ 条有向边，但最终的图仍然是无环图。 Dream 进而将一个事件抽象为图上的一个节点，将一个时代抽象为图上的一个简单路径。 Dream 认为一对事件 $(i,j)$ **可行** 当且仅当存在一个时代，使得时代的首事件是 $i$，末事件是 $j$。 Dream 现在有 $q$ 组询问。第 $i$ 组询问用两个正整数 $l_i$ 与 $r_i$ 表示，其中 $l_i\le r_i$。 Dream 想知道，对每一组询问，有多少对 **可行** 事件 $(i,j)$，使得 $i,j\in[l,r]$。

第一行两个整数 $n,m$。 接下来一行 $n-1$ 个正整数描述树的结构。第 $i$ 个数代表 $i+1$ 号节点的父亲的编号 $f_i$，也就是说存在一个 $f_i$ 往 $i$ 的一条边。 接下来 $m$ 行，每行两个正整数 $u,v$，表示一条 $u$ 往 $v$ 额外添加的边。 接下来一个正整数 $q$。 接下来 $q$ 行，每行两个正整数 $l,r$，表示一组询问。

输出 $q$ 行，每行一个整数，表示对应组询问的答案。

2 2
1
1 2
1 2
1
1 2

3

#### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（1 pts）：树形成一条链。 - Subtask 2（11 pts）：$n,q,m\le1000$。 - Subtask 3（7 pts）：$m\le 5$。 - Subtask 4（23 pts）：$n,q,m\le5\times10^4$。 - Subtask 5（17 pts）：$q\le 10^5$。 - Subtask 6（41 pts）：没有特殊限制。 对于 $100\%$ 的数据，$2\le n\le 10^5$，$0\le m\le10^5$，$1\le q\le 10^6$。 **保证** 额外添加的边不会形成环，给定的 $f_i$ 形成一颗根为 $1$ 的树。 **保证** $l\le r$。 #### 说明 [Minecraft OI Round 4](https://www.luogu.com.cn/contest/33344) C idea & solution：w33z8kqrqk8zzzx33 check：ClCN