You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给一棵边权为 $1$ 的树和一个常数 $C$，节点用 $1$ 到 $n$ 的整数表示。

定义 $dist(a,b)$ 为节点 $a,b$ 在树上的距离，即 $a$ 到 $b$ 的简单路径上的边权和，特别地，$dist(a,a) = 0$。

每次查询的时候给出一个区间 $[l,r]$，查询有多少个 C-块，定义如下：

对任意两个节点 $a,b$，定义 $a,b$ 是 C-连通的，当且仅当存在一个长为 $t$ 的节点序列 $\{v_i\}$，满足：

1. $v_1=a$
2. $v_t=b$
3. 对任意 $1\le i\le t-1$，$dist(v_i,v_{i+1})\le C$
4. 对任意 $1\le i\le t$，$l\le v_i\le r$

定义“C-块”为一个点集 $S$，满足：

1. 对任意 $a$ 属于 $S$，$b$ 属于 $S$ 的补集，$a,b$ 不 C-连通
2. 对任意 $a,b$ 属于 $S$，$a$ 和 $b$ C-连通
3. 对任意 $a$ 属于 $S$，有 $l\le a \le r$

输入格式

第一行三个数 $n$，$m$，$C$ 依次表示树的节点个数，询问次数，还有常数 $C$；

第二行共 $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$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。

10 9 2
1 1 1 2 3 4 1 1 1
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
5 5

1
1
2
3
3
3
2
1
1

提示

Idea：nzhtl1477，Solution：ccz181078，Code：nzhtl1477&ccz181078，Data：ccz181078

本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。

每个子任务的测试点满足一些特殊的限制，具体如下表：

其中，性质1、性质2的含义如下：

性质1：存在一个点 $w$ 使得 $dist(1,w)=n-1$；

性质2：$n=m$，且第 $i$ 次询问为 $l=1,\;r=i$。