注意事项

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

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

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

题目描述

题目译自 2024년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T3 「경찰과 도둑」

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 村内自由移动，速度不超过各自的最大速度。可以选择不移动。
• 如果警察和小偷在同一个位置，警察就能抓住小偷。这个位置可以是房子，也可以是道路的中间。
• 在每个场景中，警察和小偷都知道对方的速度，并且随时知道对方的位置。
• 警察和小偷都会采用最优策略。警察会尽快抓住小偷，而小偷会尽量拖延被抓住的时间。可以证明，在最优策略下，小偷一定会在有限时间内被抓住。

你需要计算每个场景中，小偷被抓住所需的时间。

实现细节

你需要实现以下函数：

vector<array<long long, 2>> police_thief(vector<int> A, vector<int> B, vector<int> D, vector<int> P, vector<int> V1, vector<int> T, vector<int> 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=4, Q=3, A=[0,0,0], B=[1,2,3], D=[557912,517656,275807]$, $P=[3,0,0], V1=[265381,190435,195025], T=[0,2,3], V2=[1000000,12345,67890]$ 的情况。

评测程序将调用如下函数：

police_thief([0, 0, 0], [1, 2, 3], [557912, 517656, 275807], [3, 0, 0], [265381, 190435, 195025], [0, 2, 3], [1000000, 12345, 67890]);

下图展示了 KOI 村的结构：

在第 $0$ 个场景中，小偷沿着通往 $1$ 号房子的路径移动，并在 $1$ 号房子被抓住。在第 $1$ 和第 $2$ 个场景中，小偷在出发的房子不动。

函数的返回值可以是 [[833719, 265381], [517656, 190435], [275807, 195025]]。其他可能的返回值包括 [[833719, 265381], [517656, 190435], [551614, 390050]]。

样例 2

考虑 $N=6, Q=4, A=[0,1,2,1,2], B=[1,2,3,4,5], D=[2,2,10,8,16]$, $P=[3,3,3,3], V1=[4,2,19,20], T=[0,0,0,0], V2=[3,1,9,19]$ 的情况。

评测程序将调用如下函数：

police_thief([0,1,2,1,2], [1,2,3,4,5], [2,2,10,8,16], [3,3,3,3], [4,2,19,20], [0,0,0,0], [3,1,9,19]);

在第 $0$ 个场景中，小偷沿着通往 $5$ 号房子的路径移动，并在连接 $2$ 号房子和 $5$ 号房子的道路中间被抓住。

函数的返回值可以是 [[6,1], [10,1], [1,1], [13,10]]。

样例 3

考虑 $N=10, Q=10, A=[4,2,9,9,3,7,1,6,5], B=[9,8,0,1,1,6,2,2,9], D=[7,8,4,5,1,2,5,10,2]$, $P=[3,0,5,2,0,5,5,7,9,8], V1=[1,6,6,5,2,6,5,4,1,5]$, $T=[5,5,9,1,6,2,0,1,8,4], V2=[9,7,6,7,4,10,10,8,7,5]$ 的情况。

评测程序将调用如下函数：

police_thief([4,2,9,9,3,7,1,6,5], [9,8,0,1,1,6,2,2,9], [7,8,4,5,1,2,5,10,2], [3,0,5,2,0,5,5,7,9,8], [1,6,6,5,2,6,5,4,1,5], [5,5,9,1,6,2,0,1,8,4], [9,7,6,7,4,10,10,8,7,5]);

下图展示了 KOI 村的结构：

函数的返回值可以是 [[18,1], [13,3], [4,1], [17,5], [13,1], [4,1], [6,5], [29,4], [22,1], [5,1]]。

样例 4

考虑 $N=10, Q=10, A=[6,8,8,3,4,9,0,1,8], B=[7,5,2,9,1,7,4,3,4], D=[1,1,4,4,4,7,3,4,7]$, $P=[3,1,6,2,3,3,2,6,1,2], V1=[5,7,9,7,5,10,8,8,4,8]$, $T=[0,7,8,0,2,0,0,7,8,5], V2=[2,2,5,5,4,5,7,2,2,7]$ 的情况。

评测程序将调用如下函数：

police_thief([6,8,8,3,4,9,0,1,8], [7,5,2,9,1,7,4,3,4], [1,1,4,4,4,7,3,4,7], [3,1,6,2,3,3,2,6,1,2], [5,7,9,7,5,10,8,8,4,8], [0,7,8,0,2,0,0,7,8,5], [2,2,5,5,4,5,7,2,2,7]);

下图展示了 KOI 村的结构：

函数的返回值可以是 [[11,5], [16,7], [31,9], [4,1], [19,5], [11,10], [31,8], [1,6], [15,4], [3,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$	无附加限制

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $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]$

注意，示例评测程序可能与实际评测程序不同。