multiverse

时限 2s - 空限 512MB

输入文件 multiverse.in - 输出文件 multiverse.out - 提交程序 multiverse.cpp

题目描述

小 D 有一颗 $n$ ($1\le n\le 7\times 10^5$)$ 节点有向树, 其中根节点为节点 $1$, 并且所有边从根节点往外延.

小 D 在这棵树上额外添加 $m$ ($0\le m\le 50$) 条有向边, 使得到的图为有向无环图.

小 D 定义一对节点 $(i,j)$ 好, 当且仅当图中存在 $i$ 到 $j$ 的路径, 而任何 $i$ 到 $j$ 的路径必须经过额外边.

小 D 有 $q$ ($1\le q\le 3\times 10^5$) 组询问, 每一组询问问: 给定 $l$ 和 $r$, 有多少好对 $(i,j)$ 使得 $l\le i<j\le r$?

输入格式

第一行两个整数 $n$ ($1\le n\le 7\times 10^5$)$和$m$ ($0\le m\le 50$), 分别为节点个数和额外边个数.

第二行 $n-1$ 个正整数, 第 $i$ 个数为节点 $i+1$ 的父亲节点 $f_i$ ($1\le f_i\le n$).

接下来 $m$ 行, 每行两个正整数 $u$ 和 $v$ ($1\le u,v\le n$), 表示一条 $u$ 向 $v$ 的额外边.

接下来一行一个正整数 $q$ ($1\le q\le 3\times 10^5$), 为询问个数.

接下来 $q$ 行, 每行两个正整数 $l$ 和 $r$ ($1\le l\le r\le n$), 表示一组询问.

输出格式

对于每一组询问, 输出一行一个非负整数, 为答案.

输入输出样例

样例 1

输入

5 1
1 1 2 2
5 3
3
1 5
2 3
4 5

输出

1
1
0

好对有 $(2,3)$ 和 $(5,3)$.

评分规定

对于 $10\%$ 的数据, $n,q\le 1000$.
对于另外 $30\%$ 的数据, $n,q\le 2\times 10^5$, $m\le 50$.
对于另外 $30\%$ 的数据, $m\le 50$.
对于 $100\%$ 的数据, $1\le n\le 7\times 10^5$, $0\le m\le 100$, $1\le q\le 3\times 10^5$, 给定的树形成一颗树, 得到的图形成一张有向无环图.