题目背景

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 将时空抽象为一颗 $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 C idea & solution：w33z8kqrqk8zzzx33 check：ClCN