P17144 [NOI 2026] 木棉

题面、样例附件来自 [QOJ](https://qoj.ac/contest/3939/problem/18987)。 提交到洛谷上时，无需引用头文件 `#include "kapok.h"`。直接将 ```cpp std::vector kapok( int c, int n, int m, std::vector a, std::vector l, std::vector r, std::vector x, std::vector y ); ``` 复制到程序开头，同时选用 C++17 或者更高版本编译器编译。

故园中的那几棵木棉，仍旧生长在小 $N$ 逐渐朦胧的记忆中。小 $N$ 对故园的记忆，可以用一个长度为 $n$ 的序列 $[a_0,a_1,\ldots,a_{n-1}]$ 表示。 故园中的每棵木棉，都形如一棵结点有标号的无根树。小 $N$ 对一棵木棉的印象，可以用她的故园记忆的一个区间 $[l,r)$ 描述： - 这棵树的结点数目为 $k=r-l+2$，结点编号为 $0\sim k-1$。 - $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ 是这棵树的 Prüfer 序列，其中 Prüfer 序列的定义详见【提示】一节。 在回忆往事时，小 $N$ 也向你提出了 $m$ 次询问。其中第 $i$（$0\le i

### 【测试程序方式】 选手可以在本题目录下使用如下命令编译得到可执行文件： ```bash g++ grader.cpp kapok.cpp -o kapok -O2 -std=c++14 -static ``` 对于编译得到的可执行文件 `kapok`： - 可执行文件将从标准输入读入以下格式的数据： - 第一行包含三个非负整数 $c,n,m$。 - 第二行包含 $n$ 个非负整数 $a_0,a_1,\ldots,a_{n-1}$。 - 第 $i+3$（$0\le i

无

### 【样例 $1$ 解释】 - 区间 $[0,3)$ 对应的树有 $5$ 个结点，Prüfer 序列为 $[2,0,2]$，边集为 $\{(1,2),(0,3),(0,2),(2,4)\}$，因此结点 $0,2$ 相邻。 - 区间 $[3,5)$ 对应的树有 $4$ 个结点，Prüfer 序列为 $[3,0]$，边集为 $\{(1,3),(0,2),(0,3)\}$，因此结点 $1,2$ 不相邻。 - 区间 $[0,0)$ 对应的树有 $2$ 个结点，Prüfer 序列为空，唯一一条边为 $(0,1)$，因此结点 $0,1$ 相邻。 ### 【样例 $2$】 见选手目录下的 `kapok/kapok2.in` 与 `kapok/kapok2.ans`。 该样例满足测试点 $3\sim5$ 的约束条件。 ### 【样例 $3$】 见选手目录下的 `kapok/kapok3.in` 与 `kapok/kapok3.ans`。 该样例满足测试点 $3\sim5$ 的约束条件。 ### 【数据范围】 对于所有测试数据，均有： - $1\le n,m\le2\times10^5$。 - 对于所有 $0\le i