Cheerio Contest 3 P5 - Train Network

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Java 3.0s
Python 3.0s
Memory limit: 512M

Problem types

In Toronto, the TTC operates a commuter train network with N stations connected by N-1 bidirectional tracks. The stations are connected such that every pair of stations are connected by travelling along a sequence of tracks. Each track takes 1 minute to traverse.

Union Station is the center of the network and is labelled node 1. Given the city's geography, all the tracks radiate outwards from downtown from west to east. The stations are numbered in ascending order based on its distance to Union Station. Stations that are at the same distance are numbered from west to east.

To improve the efficiency of the network, the TTC is considering adding a "crosstown" line, which will consist of a series of tracks that connect adjacent nodes that are the same distance from Union Station. Each track in the line will also take 1 minute to traverse. To decide on the location of the line, they decide to ask Q queries. In the ith query, they want to find the minimum time it takes for a commuter to travel from station a_i to b_i if the line was built at distance d_i. Can you write a program to answer them?


For all subtasks:

1 \le a_i, b_i, d_i \le N

a_i \ne b_i for all 1 \le i \le N

Points Awarded N Q
2 points 3 \le N \le 300 1 \le Q \le 5 \times 10^5
2 points 3 \le N \le 2 \times 10^3 1 \le Q \le 2 \times 10^3
11 points 3 \le N \le 2 \times 10^3 1 \le Q \le 5 \times 10^5

Input Specification

The first line of input contains two integers N and Q.

The next N-1 lines each contain two integers u and v, indicating a track connecting stations u and v.

The next Q lines each contain three integers a_i, b_i and d_i.

Output Specification

For each query, output the minimum time in minutes on a separate line.

Sample Input

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

Sample Output


Explanation for Sample Output

Initially, the train network looks like this:

If the line was built at distance 2 (the added tracks are coloured red), the network would look like this:

For the first query, the passenger can travel from 2 \longrightarrow 6 \longrightarrow 7 \longrightarrow 8 in 3 minutes.

For the second query, station 6 is directly connected to station 5, thus only taking 1 minute to travel.

For the third query, the passenger can travel from 5 \longrightarrow 6 \longrightarrow 7 \longrightarrow 4 in 3 minutes. Notice that the passenger can also travel from 5 \longrightarrow 2 \longrightarrow 1 \longrightarrow 4 in the same amount of time.

For the fourth query, the passenger can travel from 1 \longrightarrow 4 \longrightarrow 7 in 2 minutes. There are no stations at a distance of 4 so no new tracks would be added.


There are no comments at the moment.