Police and Thief

This problem is translated from the 2024 International Olympiad in Informatics Representative Student Selection Contest (1st Round) T3 "Police and Thief".

KOI Village consists of N houses (numbered from 0 to N-1) connected by N-1 bidirectional roads forming a tree. For each road i (0 ≤ i ≤ N-2), it connects house A[i] and house B[i] and has a length of D[i] meters.

There are Q scenarios. In scenario j (0 ≤ j ≤ Q-1):

• The police starts from house P[j] with maximum speed V1[j] m/s.
• The thief starts from house T[j] with maximum speed V2[j] m/s. (P[j] ≠ T[j])

Both police and thief may move arbitrarily along the tree (houses are points and roads are line segments). They can choose to move at any speed not exceeding their maximum speed and may even choose to remain still. They have complete information about each other’s positions and speeds at all times.

The police and the thief adopt optimal strategies – the police minimizes the catch time and the thief maximizes it. It can be proved that under these optimal strategies the thief is caught in finite time.

The key observation is that, along the unique shortest path between houses, if the police and thief choose strategies so that they meet at a point M on that path then the time until capture is given by solving:

$$\frac{d(P,M)}{V1} = \frac{d(T,M)}{V2}.$$

This gives d(P,M) = \frac{V1}{V1+V2}\,d(P,T) and d(T,M) = \frac{V2}{V1+V2}\,d(P,T), so the capture time is

$$T = \frac{d(P,M)}{V1} = \frac{d(P,T)}{V1+V2}.$$

Here, \(d(P,T)\) is the distance between the police’s and thief’s starting houses along the tree.

Your task is to implement the function police_thief which, given the village’s roads and the scenarios, returns for each scenario a fraction representing the time (in seconds) until the thief is caught. The fraction for scenario j is represented as C[j][0] / C[j][1]. Although the fraction does not have to be in simplest form, both C[j][0] and C[j][1] must be integers between 1 and 10¹⁸.

inputFormat

The function receives the following parameters:

• A, B, D: integer arrays of length N-1. For each road i, the road connects house A[i] and house B[i] and has length D[i] meters.
• P, V1, T, V2: integer arrays of length Q. For scenario j, the police starts at house P[j] with maximum speed V1[j] m/s, and the thief starts at house T[j] with maximum speed V2[j] m/s.

You should implement the following function signature (using the appropriate language syntax):

// C++ example:
std::vector<std::array> police_thief(std::vector A, std::vector B, std::vector D, std::vector P, std::vector V1, std::vector T, std::vector V2);

outputFormat

The function should return an array (of length Q) where each element is an array of 2 integers. For scenario j, if the capture time is given by the fraction C[j][0] / C[j][1] (in seconds), then both C[j][0] and C[j][1] must be between 1 and 10¹⁸. The fraction need not be in simplest terms.

sample

N = 3
A = [0, 1]
B = [1, 2]
D = [3, 4]
Q = 2
P = [0, 2]
V1 = [5, 6]
T = [2, 0]
V2 = [3, 2]

[[7,8], [7,8]]