{"problem":{"name":"[Ynoi2003] 铃原露露","description":{"content":"给定一棵有根树，顶点编号为 $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$ 在树上","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8528"},"statements":[{"statement_type":"Markdown","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以上所有数值为整数。\n\n## Input\n\n第一行两个整数 $n\\ m$；\n\n接下来一行，$n$ 个整数 $a_1,\\dots,a_n$；\n\n接下来 $n-1$ 行，依次为 $f_2,\\dots,f_n$；\n\n接下来 $m$ 行，每行 $l\\ r$ 表示一个询问。\n\n## Output\n\n对每个询问，输出一行，表示答案。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/px0y070c.png)\n\n## Note\n\nIdea：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\\%$ 的数据，无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8528","tags":["2003","O2优化","Ynoi"],"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"]],"created_at":"2026-03-03 11:09:25"}}