[THUWC 2020] 某科学的动态仙人掌

Luogu

IDLGP10302

Time6000ms

Memory512MB

DifficultyP7

2020O2优化THUWC

题目名是吸引你点进来的。给一棵边权为 $1$ 的树和一个常数 $X$，节点用 $1$ 到 $n$ 的整数表示。定义 $dist(a,b)$ 为节点 $a,b$ 在树上的距离，即 $a$ 到 $b$ 的简单路径上的边权和，特别地，$dist(a,a) = 0$。每次查询的时候给出一个区间 $[l,r]$，查询有多少个 $X$-块，定义如下：对任意两个节点 $a,b$，定义 $a,b$ 是 $X$-连通的，当且仅当存在一个长为 $t$ 的节点序列 $\{v_i\}$，其中 $t$ 可以是任意正整数，满足： 1. $v_1=a$； 2. $v_t=b$； 3. 对任意 $1\le i\le t-1$，$dist(v_i,v_{i+1})\le X$； 4. 对任意 $1\le i\le t$，$l\le v_i\le r$。定义“$X$-块”为一个点集 $S$，满足： 1. 对任意 $a$ 属于 $S$，$b$ 属于 $S$ 的补集且 $l\le b \le r$，$a,b$ 不是 X-连通的； 2. 对任意 $a,b$ 属于 $S$，$a$ 和 $b$ 是 X-连通的； 3. 对任意 $a$ 属于 $S$，有 $l\le a \le r$。 ## Input 第一行三个整数 $n$，$m$，$X$ 依次表示树的节点个数，询问次数，还有常数 $X$；第二行共 $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$。 ## Output 共 $m$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。 [samples] ## Note 本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。每个子任务的测试点满足一些特殊的限制，具体如下表： |子任务|分数|$n$|$m$|$X$|性质 1|性质 2| |:----:|:----:|:----:|:----:|:----:|:----:|:----:| |$1$|$4$|$100$|$100$|$10$|否|否| |$2$|$4$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$299999$|否|否| |$3$|$16$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$299900$|否|否| |$4$|$4$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$1$|否|否| |$5$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$2$|否|否| |$6$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$3$|否|否| |$7$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$4$|否|否| |$8$|$8$|$1\times 10 ^ 5$|$1\times 10 ^ 5$|$\le 3\times 10 ^ 5$|是|否| |$9$|$4$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$\le 3\times 10 ^ 5$|是|否| |$10$|$8$|$3\times 10 ^ 5$|$3\times 10 ^ 5$|$\le 3\times 10 ^ 5$|否|是| |$11$|$4$|$3\times 10 ^ 5$|$3\times 10 ^ 5$|$\le 3\times 10 ^ 5$|是|是| |$12$|$8$|$1\times 10 ^ 5$|$2\times 10 ^ 5$|$\le 3\times 10 ^ 5$|否|否| |$13$|$8$|$2\times 10 ^ 5$|$4\times 10 ^ 5$|$\le 3\times 10 ^ 5$|否|否| |$14$|$8$|$3\times 10 ^ 5$|$6\times 10 ^ 5$|$\le 3\times 10 ^ 5$|否|否| 其中，性质 1、性质 2 的含义如下：性质 1：存在一个点 $w$ 使得 $dist(1,w)=n-1$；性质 2：$n=m$，且第 $i$ 次询问为 $l=1,\;r=i$。

Samples

Input #1

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

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[THUWC 2020] 某科学的动态仙人掌",
    "description": {
      "content": "题目名是吸引你点进来的。 给一棵边权为 $1$ 的树和一个常数 $X$，节点用 $1$ 到 $n$ 的整数表示。 定义 $dist(a,b)$ 为节点 $a,b$ 在树上的距离，即 $a$ 到 $b$ 的简单路径上的边权和，特别地，$dist(a,a) = 0$。   每次查询的时候给出一个区间 $[l,r]$，查询有多少个 $X$-块，定义如下：   对任意两个节点 $a,b$，定义 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10302"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "题目名是吸引你点进来的。\n\n给一棵边权为 $1$ 的树和一个常数 $X$，节点用 $1$ 到 $n$ 的整数表示。\n\n定义 $dist(a,b)$ 为节点 $a,b$ 在树上的距离，即 $a$ 到 $b$ 的简单路径上的边权和，特别地，$dist(a,a) = 0$。  \n\n每次查询的时候给出一个区间 $[l,r]$，查询有多少个 $X$-块，定义如下：  \n\n对任意两个节点 $a,b$，定义 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments