{"raw_statement":[{"iden":"statement","content":"题目名是吸引你点进来的。\n\n给一棵边权为 $1$ 的树和一个常数 $X$，节点用 $1$ 到 $n$ 的整数表示。\n\n定义 $dist(a,b)$ 为节点 $a,b$ 在树上的距离，即 $a$ 到 $b$ 的简单路径上的边权和，特别地，$dist(a,a) = 0$。  \n\n每次查询的时候给出一个区间 $[l,r]$，查询有多少个 $X$-块，定义如下：  \n\n对任意两个节点 $a,b$，定义 $a,b$ 是 $X$-连通的，当且仅当存在一个长为 $t$ 的节点序列 $\\{v_i\\}$，其中 $t$ 可以是任意正整数，满足：  \n\n1. $v_1=a$；  \n2. $v_t=b$；  \n3. 对任意 $1\\le i\\le t-1$，$dist(v_i,v_{i+1})\\le X$； \n4. 对任意 $1\\le i\\le t$，$l\\le v_i\\le r$。  \n\n定义“$X$-块”为一个点集 $S$，满足：  \n\n1. 对任意 $a$ 属于 $S$，$b$ 属于 $S$ 的补集且 $l\\le b \\le r$，$a,b$ 不是 X-连通的；\n2. 对任意 $a,b$ 属于 $S$，$a$ 和 $b$ 是 X-连通的；\n3. 对任意 $a$ 属于 $S$，有 $l\\le a \\le r$。"},{"iden":"input","content":"第一行三个整数 $n$，$m$，$X$ 依次表示树的节点个数，询问次数，还有常数 $X$；\n\n第二行共 $n-1$ 个整数 $p_2\\;p_3\\;\\dots\\;p_n$，表示对于 $2 \\le i\\le n$ 的整数 $i$，$i$ 和 $p_i$ 之间有一条无向边；\n\n保证输入的数据构成一棵树；\n\n之后 $m$ 行，每行两个整数 $l\\;\\;r$，表示这次询问的区间是 $[l,r]$，保证 $l \\le r$；\n\n保证 $1 \\le n\\le 3\\cdot 10^5$，$1 \\le m\\le 6\\cdot 10^5$。"},{"iden":"output","content":"共 $m$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。"},{"iden":"note","content":"本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。\n\n每个子任务的测试点满足一些特殊的限制，具体如下表：\n\n|子任务|分数|$n$|$m$|$X$|性质 1|性质 2|\n|:----:|:----:|:----:|:----:|:----:|:----:|:----:|\n|$1$|$4$|$100$|$100$|$10$|否|否|\n|$2$|$4$|$3\\times 10 ^ 5$|$6\\times 10 ^ 5$|$299999$|否|否|\n|$3$|$16$|$3\\times 10 ^ 5$|$6\\times 10 ^ 5$|$299900$|否|否|\n|$4$|$4$|$3\\times 10 ^ 5$|$6\\times 10 ^ 5$|$1$|否|否|\n|$5$|$8$|$3\\times 10 ^ 5$|$6\\times 10 ^ 5$|$2$|否|否|\n|$6$|$8$|$3\\times 10 ^ 5$|$6\\times 10 ^ 5$|$3$|否|否|\n|$7$|$8$|$3\\times 10 ^ 5$|$6\\times 10 ^ 5$|$4$|否|否|\n|$8$|$8$|$1\\times 10 ^ 5$|$1\\times 10 ^ 5$|$\\le 3\\times 10 ^ 5$|是|否|\n|$9$|$4$|$3\\times 10 ^ 5$|$6\\times 10 ^ 5$|$\\le 3\\times 10 ^ 5$|是|否|\n|$10$|$8$|$3\\times 10 ^ 5$|$3\\times 10 ^ 5$|$\\le 3\\times 10 ^ 5$|否|是|\n|$11$|$4$|$3\\times 10 ^ 5$|$3\\times 10 ^ 5$|$\\le 3\\times 10 ^ 5$|是|是|\n|$12$|$8$|$1\\times 10 ^ 5$|$2\\times 10 ^ 5$|$\\le 3\\times 10 ^ 5$|否|否|\n|$13$|$8$|$2\\times 10 ^ 5$|$4\\times 10 ^ 5$|$\\le 3\\times 10 ^ 5$|否|否|\n|$14$|$8$|$3\\times 10 ^ 5$|$6\\times 10 ^ 5$|$\\le 3\\times 10 ^ 5$|否|否|\n \n\n其中，性质 1、性质 2 的含义如下：\n\n性质 1：存在一个点 $w$ 使得 $dist(1,w)=n-1$；\n\n性质 2：$n=m$，且第 $i$ 次询问为 $l=1,\\;r=i$。"}],"translated_statement":null,"sample_group":[["10 9 2\n1 1 1 2 3 4 1 1 1\n1 3\n2 4\n3 5\n4 6\n5 7\n6 8\n7 9\n8 10\n5 5\n","1\n1\n2\n3\n3\n3\n2\n1\n1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}