P7126 [Ynoi2008] rdCcot

Given a tree whose edge weights are all $1$ and a constant $C$. The nodes are labeled by 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 $C$-blocks there are, defined as follows: For any two nodes $a,b$, define that $a$ and $b$ are $C$-connected if and only if there exists a node sequence $\{v_i\}$ of length $t$ 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 C$. 4. For any $1\le i\le t$, $l\le v_i\le r$. Define a "$C$-block" as a set of nodes $S$ such that: 1. For any $a\in S$ and any $b$ in the complement of $S$, $a$ and $b$ are not $C$-connected. 2. For any $a,b\in S$, $a$ and $b$ are $C$-connected. 3. For any $a\in S$, $l\le a\le r$.

The first line contains three numbers $n$, $m$, $C$, representing the number of nodes in the tree, the number of queries, and the constant $C$, respectively. The second line contains $n-1$ numbers $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 numbers $l\;\;r$, indicating that the interval of this query is $[l,r]$, and 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. Each line contains one integer, representing the answer to that query.

Idea: nzhtl1477, Solution: ccz181078, Code: nzhtl1477&ccz181078, Data: ccz181078. This problem has multiple subtasks. Each subtask may contain multiple test points. 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 restrictions, as shown in the table below:  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 in the $i$-th query, $l=1,\;r=i$. Translated by ChatGPT 5