QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 7456. rdCcot

统计

给一棵边权为 $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

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

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

子任务 分数 $n \leq$ $m \leq $ $C$ 性质 1 性质 2
$1$ $4$ $100$ $100$ $\leq 10$
$2$ $4$ $3 \times 10^5$ $6 \times 10^5$ $= 299\,999$
$3$ $16$ $= 299\,900$
$4$ $4$ $= 1$
$5$ $8$ $\leq 2$
$6$ $8$ $\leq 3$
$7$ $8$ $\leq 4$
$8$ $8$ $10^5$ $10^5$ $\leq 3 \times 10^5$
$9$ $4$ $3 \times 10^5$ $6 \times 10^5$
$10$ $8$ $3 \times 10^5$
$11$ $4$
$12$ $8$ $10^5$ $2 \times 10^5$
$13$ $8$ $2 \times 10^5$ $4 \times 10^5$
$14$ $8$ $3 \times 10^5$ $6 \times 10^5$

其中,性质1、性质2的含义如下:

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

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