AdditionalFile5572.zip

#5572. 「RMI 2025」Engineers

标签: 传统 | 时间限制: 2250 ms | 内存限制: 512 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "engineers.h"。

题目描述

题目译自 Romanian Master of Informatics 2025 Day1 T1 「Engineers」

Vianu 的年度服务器维护时间到了。有些维护工作可以由人工完成，但连接网络的电缆穿过一系列太小而无法进入的地下管道！幸运的是，一位才华横溢的工程师想出了一个主意：让受过训练的老鼠来检查计算机。

每只老鼠可以从一台计算机进入网络，沿着地下管道中的电缆行进，并从另一台计算机离开，沿途检查所有计算机。因为老鼠很懒，每只老鼠在累倒之前只会沿着起点和终点之间的一条简单路径行进。

维护人员希望老鼠检查一些计算机，以便在剩余未检查的计算机中，安全代码的配置是足够平衡的。你的任务是确定所需的最少老鼠数量。

有 $N$ 台计算机，编号从 $0$ 到 $N-1$，通过 $N-1$ 条电缆连接。网络是一棵树（连通且无环）。

一只老鼠可以检查它进入网络的计算机和它离开的计算机之间唯一的简单路径上的所有计算机。形式上，如果一只老鼠在计算机 $S$ 进入并在计算机 $T$ 离开（$S, T \in \{0, \ldots, N-1\}$），那么老鼠将检查满足以下条件的所有计算机 $v_{1}, v_{2}, \ldots, v_{k}$：

• $v_{1}=S$ 且 $v_{k}=T$，
• 对于所有 $1 \leq i < k$，计算机 $v_{i}$ 和 $v_{i+1}$ 通过电缆直接相连，
• $k$ 是最小的。

老鼠可以重复使用相同的电缆和计算机，一台计算机也可以被多只老鼠检查。

每台计算机 $i \in \{0, \ldots, N-1\}$ 都有一个关联的正整数代码 $C_{i} \geq 1$。维护人员设定了一个最大可接受差值 $D$。在所有老鼠完成工作后，设剩余未检查的计算机集合为 $R \subseteq \{0, \ldots, N-1\}$。工作人员希望确保对于 $R$ 中的任意一对 $i, j$，都有 $|C_{i}-C_{j}| \leq D$。

换句话说，剩余计算机中最大代码和最小代码之间的差值必须不超过 $D$。

每只老鼠在累倒之前只能检查一条路径。你希望最小化使用的老鼠数量。

实现细节

你应该实现以下函数：

int solve(int N, int D, std::vector<int> C, std::vector<int> P, std::vector<int> Q)

此函数接收以下参数：

• $N$：计算机的数量。
• $D$：最大可接受差值。
• $C$：计算机的代码。
• 两个长度为 $N-1$ 的向量 $P$ 和 $Q$：表示对于所有 $0 \leq i \leq N-1$，计算机 $P_{i}$ 和 $Q_{i}$ 之间有一条电缆。

函数应返回所需的最少老鼠数量，以便在所有老鼠检查完路径后，剩余未检查的计算机满足：

$$\max _{i \in R} C_{i}-\min _{i \in R} C_{i} \leq D$$

样例 1

输入

5 
aabaabacbbaabaa

输出

7

在第一个样例中，有 $N=5$ 台计算机和 $D=3$。网络图示如下：

样例 2

输入

8 
aaaaaaaaaaaaaaaaaaa

输出

4

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 200000$。
• 对于所有 $0 \leq i \leq N-1$，满足 $1 \leq C_{i} \leq 1000000000$。
• $1 \leq D \leq 1000000000$。
• $0 \leq p_{i}, q_{i} < N, p_{i} \neq q_{i}$，且所有对 $(p_{i}, q_{i})$ 都是不同的。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$7$	$N \leq 20$ 且对于所有 $0 \leq i \leq N-1$，满足 $1 \leq C_{i} \leq 50$。
$2$	$6$	$N \leq 1000$ 且对于所有 $0 \leq i \leq N-1$，满足 $1 \leq C_{i} \leq 1000$。
$3$	$11$	$N \leq 1000$。
$4$	$16$	对于所有 $0 \leq i < N-1$，满足 $p_{i}=0, q_{i}=i+1$。
$5$	$26$	$N \leq 50000$。
$6$	$34$	无附加限制。