{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/px0y070c.png)"},{"iden":"statement","content":"给定一棵有根树，顶点编号为 $1,2,\\dots,n$，对 $2\\le i\\le n$ 有 $f_{i}$ 为 $i$ 的父亲。$a_1,\\dots,a_n$ 是 $1,\\dots,n$ 的排列。\n\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\n以上所有数值为整数。"},{"iden":"input","content":"第一行两个整数 $n\\ m$；\n\n接下来一行，$n$ 个整数 $a_1,\\dots,a_n$；\n\n接下来 $n-1$ 行，依次为 $f_2,\\dots,f_n$；\n\n接下来 $m$ 行，每行 $l\\ r$ 表示一个询问。"},{"iden":"output","content":"对每个询问，输出一行，表示答案。"},{"iden":"note","content":"Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078\n\n对于 $100\\%$ 的数据，满足 $1\\le n,m\\le 2\\times 10^5$，$1\\le f_i\\le i-1$，$l\\le r$。\n\n对于 $25\\%$ 的数据，满足 $n,m\\le 100$。\n\n对于另外 $25\\%$ 的数据，满足 $n,m\\le 3000$。\n\n对于另外 $25\\%$ 的数据，满足 $l=1,\\;r=n,\\;m=1$。\n\n对于另外 $25\\%$ 的数据，无特殊限制。\n\n"}],"translated_statement":null,"sample_group":[["5 5\n2 5 1 3 4\n1\n2\n3\n4\n1 1\n1 4\n3 3\n2 2\n1 1","1\n10\n1\n1\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}