题目背景

请勿使用 C++14 (GCC 9) 提交。

你需要在程序开头加入如下代码：

#include<vector>
#include<array>
std::vector<std::array<long long, 2>> police_thief(std::vector<int> A, std::vector<int> B, std::vector<int> D, std::vector<int> P, std::vector<int> V1, std::vector<int> T, std::vector<int> V2);

题目描述

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

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

你需要实现以下函数：

std::vector<std::array<long long, 2>> police_thief(std::vector<int> A, std::vector<int> B, std::vector<int> D, std::vector<int> P, std::vector<int> V1, std::vector<int> T, std::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\,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]$

4 3
0 1 557912
0 2 517656
0 3 275807
3 265381 0 1000000
0 190435 2 12345
0 195025 3 67890

833719 265381
517656 190435
275807 195025

6 4
0 1 2
1 2 2
2 3 10
1 4 8
2 5 16
3 4 0 3
3 2 0 1
3 19 0 9
3 20 0 19

6 1
10 1
1 1
13 10

10 10
4 9 7
2 8 8
9 0 4
9 1 5
3 1 1
7 6 2
1 2 5
6 2 10
5 9 2
3 1 5 9
0 6 5 7
5 6 9 6
2 5 1 7
0 2 6 4
5 6 2 10
5 5 0 10
7 4 1 8
9 1 8 7
8 5 4 5

18 1
13 3
4 1
17 5
13 1
4 1
6 5
29 4
22 1
5 1

10 10
6 7 1
8 5 1
8 2 4
3 9 4
4 1 4
9 7 7
0 4 3
1 3 4
8 4 7
3 5 0 2
1 7 7 2
6 9 8 5
2 7 0 5
3 5 2 4
3 10 0 5
2 8 0 7
6 8 7 2
1 4 8 2
2 8 5 7

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$		对于所有 $j$ $(0 \leq j \leq Q-1)$，$P[j]=0$
$8$	$10$	对于所有 $j$ $(0 \leq j \leq Q-1)$，$T[j]=0$
$9$	$11$	无附加限制