警察与小偷

题目描述

KOI 村由 $N$ 座房子和连接这些房子的 $N-1$ 条双向道路组成。任意两座不同的房子都可以通过这些道路互相到达。也就是说，KOI 村的道路网络是一棵树。

KOI 村的房子编号为 $0,1,\ldots,N-1$，道路编号为 $0,1,\ldots,N-2$。对于编号为 $i$ 的道路，它连接房子 $A[i]$ 和 $B[i]$，长度为 $D[i]$ 米。

最近，KOI 村频繁发生盗窃事件，村民们十分困扰。为了应对这种情况，村里决定在某个房子里安排警察待命，以便在小偷出现时迅速抓捕。村民们想知道在不同情况下，警察需要多长时间才能抓住小偷。

你会得到 $Q$ 个场景，场景编号为 $0,1,\ldots,Q-1$。在第 $j$ 个场景中：

• 警察从编号为 $P[j]$ 的房子出发，最大速度为 $V1[j]$ 米/秒；
• 小偷从编号为 $T[j]$ 的房子出发，最大速度为 $V2[j]$ 米/秒；
• 警察和小偷的出发房子不同，即 $P[j] \ne 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$。对于每个 $0 \le j < Q$，$C[j]$ 是一个包含两个整数的数组，表示第 $j$ 个场景中小偷被抓住所需时间为：

$$\frac{C[j][0]}{C[j][1]}$$

秒。

该分数不要求约分，但必须与真实答案相等，并且 $C[j][0]$ 和 $C[j][1]$ 都必须是 $1$ 到 $10^{18}$ 之间的整数。

提交的代码中不应包含任何标准输入输出操作。

---

样例评测程序的输入格式

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

第一行包含两个整数 $N,Q$。

接下来 $N-1$ 行，每行包含三个整数 $A[i],B[i],D[i]$，表示第 $i$ 条道路连接房子 $A[i]$ 和 $B[i]$，长度为 $D[i]$ 米。

接下来 $Q$ 行，每行包含四个整数 $P[j],V1[j],T[j],V2[j]$，表示第 $j$ 个场景中，警察从房子 $P[j]$ 出发，最大速度为 $V1[j]$ 米/秒；小偷从房子 $T[j]$ 出发，最大速度为 $V2[j]$ 米/秒。

---

样例评测程序的输出格式

假设 police_thief 返回的数组为 $C$。样例评测程序将输出 $Q$ 行。

第 $j+1$ 行输出两个整数 $C[j][0]$ 和 $C[j][1]$，表示第 $j$ 个场景的答案为：

$$\frac{C[j][0]}{C[j][1]}$$

秒。

---

输入输出样例 #1

输入 #1

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

输出 #1

833719 265381
517656 190435
275807 195025

---

输入输出样例 #2

输入 #2

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

输出 #2

6 1
10 1
1 1
13 10

---

输入输出样例 #3

输入 #3

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

输出 #3

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

---

输入输出样例 #4

输入 #4

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

输出 #4

11 5
16 7
31 9
4 1
19 5
11 10
31 8
1 6
15 4
3 1

---

数据范围

对于所有测试数据，满足：

• $2 \le N \le 10^5$；
• $1 \le Q \le 10^5$；
• 对于所有 $0 \le i \le N-2$，$0 \le A[i],B[i] \le N-1$；
• 对于所有 $0 \le i \le N-2$，$A[i] \ne B[i]$；
• 对于所有 $0 \le i \le N-2$，$1 \le D[i] \le 10^6$；
• 给出的道路网络是一棵树；
• 对于所有 $0 \le j \le Q-1$，$0 \le P[j],T[j] \le N-1$；
• 对于所有 $0 \le j \le Q-1$，$P[j] \ne T[j]$；
• 对于所有 $0 \le j \le Q-1$，$1 \le V1[j],V2[j] \le 10^6$。

---

子任务

子任务	分值	附加限制
$1$	$15$	$N \le 5000,\ Q \le 5000$
$2$	$21$	$N \le 50000,\ Q \le 50000$
$3$	$5$	对于所有 $0 \le i \le N-2$，$A[i]=i,\ B[i]=i+1$
$4$	$6$	对于所有 $0 \le i \le N-2$，$A[i]=0,\ B[i]=i+1$
$5$	$14$	对于所有 $0 \le j \le Q-1$，$V1[j] \le V2[j]$
$6$	$9$	对于所有 $0 \le j \le Q-1$，$P[j]$ 和 $T[j]$ 之间的道路数量不超过 $10$ 条
$7$		对于所有 $0 \le j \le Q-1$，$P[j]=0$
$8$	$10$	对于所有 $0 \le j \le Q-1$，$T[j]=0$
$9$	$11$	无附加限制