P10302 [THUWC 2020] A Certain Scientific Dynamic Cactus.

The title is just to attract you to click in. You are given a tree whose edge weights are $1$, and a constant $X$. The nodes are labeled with integers from $1$ to $n$. Define $dist(a,b)$ as the distance between nodes $a$ and $b$ on the tree, i.e. the sum of edge weights on the simple path from $a$ to $b$. In particular, $dist(a,a)=0$. In each query, an interval $[l,r]$ is given. You need to ask how many $X$-blocks there are, defined as follows. For any two nodes $a,b$, define that $a$ and $b$ are $X$-connected if and only if there exists a node sequence $\{v_i\}$ of length $t$, where $t$ can be any positive integer, such that: 1. $v_1=a$; 2. $v_t=b$; 3. For any $1 \le i \le t-1$, $dist(v_i,v_{i+1}) \le X$; 4. For any $1 \le i \le t$, $l \le v_i \le r$. Define an "$X$-block" as a set of nodes $S$ satisfying: 1. For any $a \in S$ and any $b$ in the complement of $S$ with $l \le b \le r$, $a$ and $b$ are not $X$-connected; 2. For any $a,b \in S$, $a$ and $b$ are $X$-connected; 3. For any $a \in S$, $l \le a \le r$.

The first line contains three integers $n$, $m$, $X$, denoting the number of nodes in the tree, the number of queries, and the constant $X$, respectively. The second line contains $n-1$ integers $p_2\;p_3\;\dots\;p_n$, meaning that for each integer $i$ with $2 \le i \le n$, there is an undirected edge between $i$ and $p_i$. It is guaranteed that the input forms a tree. Then follow $m$ lines, each containing two integers $l\;\;r$, meaning the interval of this query is $[l,r]$. It is guaranteed that $l \le r$. Constraints: $1 \le n \le 3 \cdot 10^5$, $1 \le m \le 6 \cdot 10^5$.

Output $m$ lines, answering the queries in order. For each query, output one integer per line, which is the answer to this query.

This problem has multiple subtasks. Each subtask may contain multiple test points, and you can get the score of a subtask only if you pass all test points in that subtask. The test points of each subtask satisfy some special constraints, as shown in the table below: |Subtask|Score|$n$|$m$|$X$|Property 1|Property 2| |:----:|:----:|:----:|:----:|:----:|:----:|:----:| |$1$|$4$|$100$|$100$|$10$|No|No| |$2$|$4$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$299999$|No|No| |$3$|$16$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$299900$|No|No| |$4$|$4$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$1$|No|No| |$5$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$2$|No|No| |$6$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$3$|No|No| |$7$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$4$|No|No| |$8$|$8$|$1\times 10 ^ 5$|$1\times 10 ^ 5$|$\le 3\times 10 ^ 5$|Yes|No| |$9$|$4$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$\le 3\times 10 ^ 5$|Yes|No| |$10$|$8$|$3\times 10 ^ 5$|$3\times 10 ^ 5$|$\le 3\times 10 ^ 5$|No|Yes| |$11$|$4$|$3\times 10 ^ 5$|$3\times 10 ^ 5$|$\le 3\times 10 ^ 5$|Yes|Yes| |$12$|$8$|$1\times 10 ^ 5$|$2\times 10 ^ 5$|$\le 3\times 10 ^ 5$|No|No| |$13$|$8$|$2\times 10 ^ 5$|$4\times 10 ^ 5$|$\le 3\times 10 ^ 5$|No|No| |$14$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$\le 3\times 10 ^ 5$|No|No| Here, the meanings of Property 1 and Property 2 are as follows. Property 1: There exists a node $w$ such that $dist(1,w)=n-1$. Property 2: $n=m$, and for the $i$-th query, $l=1,\;r=i$. Translated by ChatGPT 5