QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 7439. 铃原露露

统计

给定一棵有根树,顶点编号为 $1,2,\dots,n$,对 $2\le i\le n$ 有 $f_{i}$ 为 $i$ 的父亲。$a_1,\dots,a_n$ 是 $1,\dots,n$ 的排列。

共 $m$ 次询问,每次询问给出 $l,r$,询问有多少个二元组 $L,R$,满足 $l\le L\le R\le r$,且对任意 $L\le a_x\le a_y\le R$,有 $x,y$ 在树上的最近公共祖先 $z$ 满足 $L\le a_z\le R$。

以上所有数值为整数。

输入格式

第一行两个整数 $n\ m$;

接下来一行,$n$ 个整数 $a_1,\dots,a_n$;

接下来 $n-1$ 行,依次为 $f_2,\dots,f_n$;

接下来 $m$ 行,每行 $l\ r$ 表示一个询问。

输出格式

对每个询问,输出一行,表示答案。

样例数据

样例输入

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

样例输出

1
10
1
1
1

子任务

Idea:nzhtl1477,Solution:ccz181078,Code:ccz181078,Data:ccz181078

对于 $100\%$ 的数据,满足 $1\le n,m\le 2\times 10^5$,$1\le f_i\le i-1$,$l\le r$。

对于 $25\%$ 的数据,满足 $n,m\le 100$。

对于另外 $25\%$ 的数据,满足 $n,m\le 3000$。

对于另外 $25\%$ 的数据,满足 $l=1,\;r=n,\;m=1$。

对于另外 $25\%$ 的数据,无特殊限制。