P11237 [KTSC 2024 R1] 警察与小偷

**请勿使用 C++14 (GCC 9) 提交**。 你需要在程序开头加入如下代码： ```cpp #include #include std::vector police_thief(std::vector A, std::vector B, std::vector D, std::vector P, std::vector V1, std::vector T, std::vector V2); ```

**题目译自 [2024년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2024/) T3 「[경찰과 도둑](https://assets.ioikorea.kr/ioitst/2024/1/police/police_statement.pdf)」** KOI 村由 $N$ 座房子和连接这些房子的 $N-1$ 条双向道路组成。任意两座不同的房子都可以通过这些道路互相到达。也就是说，KOI 村的道路网络是一个树结构。 KOI 村的房子编号从 $0$ 到 $N-1$，道路编号从 $0$ 到 $N-2$。对于编号为 $i$ 的道路，它连接了编号为 $A[i]$ 和 $B[i]$ 的房子，长度为 $D[i]$ 米。 最近，KOI 村频繁发生盗窃事件，村民们非常困扰。为了应对这种情况，村里决定在某个房子里安排警察待命，以便在小偷出现时迅速抓捕。村民们想知道在不同情况下，警察需要多长时间才能抓住小偷。 你将会得到 $Q$ 个场景，每个场景编号从 $0$ 到 $Q-1$。每个场景如下： - 在第 $j$ 个场景中，警察从编号为 $P[j]$ 的房子出发，最大速度为 $V1[j]$ 米/秒。 - 在第 $j$ 个场景中，小偷从编号为 $T[j]$ 的房子出发，最大速度为 $V2[j]$ 米/秒。 - 警察和小偷出发的房子不同，即 $P[j] \neq T[j]$。 - 房子的大小可以忽略不计，因此可以将房子视为一个点。道路的宽度也可以忽略不计，因此可以将道路视为一条线段。道路之间不相交。 - 警察和小偷可以在 KOI 村内自由移动，速度不超过各自的最大速度。可以选择不移动。 - 如果警察和小偷在同一个位置，警察就能抓住小偷。这个位置可以是房子，也可以是道路的中间。 - 在每个场景中，警察和小偷都知道对方的速度，并且随时知道对方的位置。 - 警察和小偷都会采用最优策略。警察会尽快抓住小偷，而小偷会尽量拖延被抓住的时间。可以证明，在最优策略下，小偷一定会在有限时间内被抓住。 你需要计算每个场景中，小偷被抓住所需的时间。 你需要实现以下函数： ```cpp std::vector police_thief(std::vector A, std::vector B, std::vector D, std::vector P, std::vector V1, std::vector T, std::vector V2); ``` - `A, B, D`：大小为 $N-1$ 的整数数组。对于每条编号为 $i$ 的道路，它连接了编号为 $A[i]$ 和 $B[i]$ 的房子，长度为 $D[i]$ 米。 - `P, V1, T, V2`：大小为 $Q$ 的整数数组。对于第 $j$ 个场景，警察从编号为 $P[j]$ 的房子出发，最大速度为 $V1[j]$ 米/秒，小偷从编号为 $T[j]$ 的房子出发，最大速度为 $V2[j]$ 米/秒。 - 该函数返回一个大小为 $Q$ 的数组 $C$，每个元素是一个大小为 $2$ 的数组。对于第 $j$ 个场景，小偷被抓住所需的时间（以秒为单位）表示为分数 $C[j][0] / C[j][1]$。 - $C[j][0] / C[j][1]$ 可以不是最简分数，但 $C[j][0]$ 和 $C[j][1]$ 必须是 $1$ 到 $10^{18}$ 之间的整数。可以证明，对于所有满足约束条件的输入，答案总能表示为这种形式的分数。 注意，提交的代码中不应包含任何输入输出操作。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N\,Q$ - 第 $2+i$ $(0 \leq i \leq N-2)$ 行：$A[i]\,B[i]\,D[i]$ - 第 $1+N+j$ $(0 \leq j \leq Q-1)$ 行：$P[j]\,V1[j]\,T[j]\,V2[j]$

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N\,Q$ - 第 $2+i$ $(0 \leq i \leq N-2)$ 行：$A[i]\,B[i]\,D[i]$ - 第 $1+N+j$ $(0 \leq j \leq Q-1)$ 行：$P[j]\,V1[j]\,T[j]\,V2[j]$ 假设 `police_thief` 返回的数组为 $C$。示例评测程序将输出： - 第 $1+j$ $(0 \leq j \leq Q-1)$ 行：$C[j][0]\,C[j][1]$

对于所有输入数据，满足： - $2 \leq N \leq 10^5$ - $1 \leq Q \leq 10^5$ - 对于所有 $i$ $(0 \leq i \leq N-2)$，$0 \leq A[i], B[i] \leq N-1$ 且 $A[i] \neq B[i]$ - 对于所有 $i$ $(0 \leq i \leq N-2)$，$1 \leq D[i] \leq 10^6$ - KOI 村是一棵树的结构 - 对于所有 $j$ $(0 \leq j \leq Q-1)$，$0 \leq P[j], T[j] \leq N-1$ 且 $P[j] \neq T[j]$ - 对于所有 $j$ $(0 \leq j \leq Q-1)$，$1 \leq V1[j], V2[j] \leq 10^6$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $15$ | $N \leq 5000, Q \leq 5000$ | | $2$ | $21$ | $N \leq 50000,Q \leq 50000$ | | $3$ | $5$ | 对于所有 $i$ $(0 \leq i \leq N-2)$，$A[i]=i, B[i]=i+1$ | | $4$ | $6$ | 对于所有 $i$ $(0 \leq i \leq N-2)$，$A[i]=0, B[i]=i+1$ | | $5$ | $14$ | 对于所有 $j$ $(0 \leq j \leq Q-1)$，$V1[j] \leq V2[j]$ | | $6$ | $9$ | 对于所有 $j$ $(0 \leq j \leq Q-1)$，$P[j]$ 和 $T[j]$ 之间的道路数量不超过 $10$ 条 | | $7$ | $9$ | 对于所有 $j$ $(0 \leq j \leq Q-1)$，$P[j]=0$ | | $8$ | $10$ | 对于所有 $j$ $(0 \leq j \leq Q-1)$，$T[j]=0$ | | $9$ | $11$ | 无附加限制 |