P10302 [THUWC 2020] 某科学的动态仙人掌

题目名是吸引你点进来的。 给一棵边权为 $1$ 的树和一个常数 $X$，节点用 $1$ 到 $n$ 的整数表示。 定义 $dist(a,b)$ 为节点 $a,b$ 在树上的距离，即 $a$ 到 $b$ 的简单路径上的边权和，特别地，$dist(a,a) = 0$。 每次查询的时候给出一个区间 $[l,r]$，查询有多少个 $X$-块，定义如下： 对任意两个节点 $a,b$，定义 $a,b$ 是 $X$-连通的，当且仅当存在一个长为 $t$ 的节点序列 $\{v_i\}$，其中 $t$ 可以是任意正整数，满足： 1. $v_1=a$； 2. $v_t=b$； 3. 对任意 $1\le i\le t-1$，$dist(v_i,v_{i+1})\le X$； 4. 对任意 $1\le i\le t$，$l\le v_i\le r$。 定义“$X$-块”为一个点集 $S$，满足： 1. 对任意 $a$ 属于 $S$，$b$ 属于 $S$ 的补集且 $l\le b \le r$，$a,b$ 不是 X-连通的； 2. 对任意 $a,b$ 属于 $S$，$a$ 和 $b$ 是 X-连通的； 3. 对任意 $a$ 属于 $S$，有 $l\le a \le r$。

第一行三个整数 $n$，$m$，$X$ 依次表示树的节点个数，询问次数，还有常数 $X$； 第二行共 $n-1$ 个整数 $p_2\;p_3\;\dots\;p_n$，表示对于 $2 \le i\le n$ 的整数 $i$，$i$ 和 $p_i$ 之间有一条无向边； 保证输入的数据构成一棵树； 之后 $m$ 行，每行两个整数 $l\;\;r$，表示这次询问的区间是 $[l,r]$，保证 $l \le r$； 保证 $1 \le n\le 3\cdot 10^5$，$1 \le m\le 6\cdot 10^5$。

共 $m$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。

本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。 每个子任务的测试点满足一些特殊的限制，具体如下表： |子任务|分数|$n$|$m$|$X$|性质 1|性质 2| |:----:|:----:|:----:|:----:|:----:|:----:|:----:| |$1$|$4$|$100$|$100$|$10$|否|否| |$2$|$4$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$299999$|否|否| |$3$|$16$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$299900$|否|否| |$4$|$4$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$1$|否|否| |$5$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$2$|否|否| |$6$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$3$|否|否| |$7$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$4$|否|否| |$8$|$8$|$1\times 10 ^ 5$|$1\times 10 ^ 5$|$\le 3\times 10 ^ 5$|是|否| |$9$|$4$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$\le 3\times 10 ^ 5$|是|否| |$10$|$8$|$3\times 10 ^ 5$|$3\times 10 ^ 5$|$\le 3\times 10 ^ 5$|否|是| |$11$|$4$|$3\times 10 ^ 5$|$3\times 10 ^ 5$|$\le 3\times 10 ^ 5$|是|是| |$12$|$8$|$1\times 10 ^ 5$|$2\times 10 ^ 5$|$\le 3\times 10 ^ 5$|否|否| |$13$|$8$|$2\times 10 ^ 5$|$4\times 10 ^ 5$|$\le 3\times 10 ^ 5$|否|否| |$14$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$\le 3\times 10 ^ 5$|否|否| 其中，性质 1、性质 2 的含义如下： 性质 1：存在一个点 $w$ 使得 $dist(1,w)=n-1$； 性质 2：$n=m$，且第 $i$ 次询问为 $l=1,\;r=i$。