# KOITST 24 Police and Thief

https://www.acmicpc.net/problem/31285

KOI Village consists of $N$ houses connected by $N - 1$ bidirectional roads, and any two different houses can be reached using only roads. In other words, the road network of KOI Village forms a tree structure.

The houses in KOI Village are numbered from $0$ to $N - 1$, and the roads in KOI Village are numbered from $0$ to $N - 2$. For all $0 \leq i \leq N - 2$, road $i$ connects house $A[i]$ and house $B[i]$ with a length of $D[i]$ meters.

Recently, the residents of KOI Village have been experiencing difficulties due to frequent burglaries. Therefore, they want to station the police at one house in KOI Village to prepare for the appearance of burglars. The people of KOI Village became curious about how quickly the police could catch the burglars in the event of a burglary.

You are given $Q$ scenarios. Each scenario is numbered from $0$ to $Q - 1$. A scenario consists of the following:

In scenario $j$:

* The police start from house $P[j]$ and can move at most $V1[j]$ meters per second.
* The thief starts from house $T[j]$ and can move at most $V2[j]$ meters per second.
* The houses where the police and the thief start are different. That is, $P[j] \neq T[j]$.
* Since the size of the houses is small enough, consider them as points. Since the width of the roads is narrow enough, consider them as line segments. The roads do not intersect.
* The police and the thief can move freely within KOI Village within their maximum speeds. Not moving is also possible.
* If the police and the thief are at the same location, the police can catch the thief. In this case, the police can catch the thief not only at houses but also at points along the roads.
* At any point in the scenario, the police and the thief know each other's speeds and can know each other's locations.
* The police and the thief use the best strategy. That is, the police use the strategy to catch the thief as quickly as possible, and the thief uses the strategy to escape for the longest time. When the police and the thief use the best strategy, it can be proven that the thief will be caught within a finite time.

For each scenario, you need to find the time it takes for the thief to be caught.

# Function List and Definitions

You must implement the following function:

`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$: Arrays of size $N - 1$ of integers. For all $0 \leq i \leq N - 2$, road $i$ connects house $A[i]$ and house $B[i]$ with a length of $D[i]$ meters.

$P$, $V1$, $T$, $V2$: Arrays of size $Q$ of integers. For all $0 \leq j \leq Q - 1$, in scenario $j$, the police start from house $P[j]$ and can move at most $V1[j]$ meters per second, and the thief starts from house $T[j]$ and can move at most $V2[j]$ meters per second.

This function should return an array $C$ of size $Q$, where each element $C[j]$ is an array of size $2$. For all $0 \leq j \leq Q -1$, the time (in seconds) it takes for the thief to be caught in scenario $j$ should be represented in the form $C[j][0]/C[j][1]$.

$C[j][0]/C[j][1]$ does not have to be in reduced form. However, $C[j][0]$ and $C[j][1]$ must be integers between $1$ and $10^{18}$. It can be proven that for all inputs satisfying the constraints, the answer can always be represented in this form.

# Constraints

$2 \leq N \leq 100,000$
$1 \leq Q \leq 100,000$
For all $0 \leq i \leq N - 2$, $0 \leq A[i], B[i] \leq N - 1$, $A[i] \neq B[i]$
For all $0 \leq i \leq N - 2$, $1 \leq D[i] \leq 1,000,000$
KOI Village forms a tree structure.
For all $0 \leq j \leq Q - 1$, $0 \leq P[j], T[j] \leq N - 1$, $P[j] \neq T[j]$
For all $0 \leq j \leq Q - 1$, $1 \leq V1[j], V2[j] \leq 1,000,000$


subtask 6: The number of roads on a simple path connecting house $P[j]$ and house $T[j]$ is less than or equal to 10.

# Examples

Example 1:

Consider the case where $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]$.

The grader calls the function as follows:

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

The diagram below represents the structure of KOI Village:


In scenario 0, the thief moves along the path towards house 1 and gets caught at house 1. In scenarios 1 and 2, the thief doesn't move from the starting house.

Possible return values for the function are $[[833719, 265381], [517656, 190435], [275807, 195025]]$. Other possible return values include $[[833719, 265381], [517656, 190435], [551614, 390050]]$, and so on.

Example 2:

Consider the case where $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]$.

The grader calls the function as follows:

`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])`

The diagram below represents the structure of KOI Village:


In scenario 0, the thief moves along the path towards house 5 and gets caught at the midpoint of the road connecting houses 2 and 5.

Possible return values for the function are $[[6, 1], [10, 1], [1, 1], [13, 10]]$.

Example 3:

Consider the case where $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]$.

The grader calls the function as follows:

`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])`

The diagram below represents the structure of KOI Village:


Possible return values for the function are $[[18, 1], [13, 3], [4, 1], [17, 5], [13, 1], [4, 1], [6, 5], [29, 4], [22, 1], [5, 1]]$.

Example 4:

Consider the case where $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]$.

The grader calls the function as follows:

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])

The diagram below represents the structure of KOI Village:


Possible return values for the function are $[[11, 5], [16, 7], [31, 9], [4, 1], [19, 5], [11, 10], [31, 8], [1, 6], [15, 4], [3, 1]]$.