G.W. Coding Contest 3 P6: Evil Questions Attacking Ontario

At Dr. G.W. Williams S.S, Each of the \(N\) classrooms can be represented by a number from 1 to \(N\), with 1 being the main entrance. There are also \(N-1\) hallways, each stemming out from the main entrance connecting different pairs of classrooms both ways. Each hallway takes 1 minute to traverse.

1. There are some number of "layers" to the school (not physical floors)
2. Each of the \(N\) classrooms are grouped in one of these layers, e.g. classrooms 2, 3 and 4 may be on layer 1.
3. Each layer is defined as the number of minutes to get to that layer from the main entrance. i.e. if classrooms 2, 3 and 4 are on layer 1, it takes 1 minute to get to them at the shortest from the main entrance.
4. The classroom numbers are sorted by west to east, meaning if only classrooms 2, 3 and 4 are on layer 1, then 2 is the west most classroom on that layer while 4 is the east most.
5. The classroom numbers are also sorted by layer, meaning if classroom 4 is the last classroom on layer 1, then on layer 2 the first classroom must be classroom number 5.
6. The main entrance is on a layer by itself.

It is possible to reach any classroom from any classroom using this layout.

Unfortunately EQAO is starting, and the school closes some number of classrooms per day for each of the \(D\) days of EQAO so that you cannot travel through these classrooms. This makes it possible to not be able to reach every classroom. To try to combat this, the school architects have decided to build a temporary hallway every day to connect each of the classrooms at layer \(L\) from west to east.

Annoyingly, your friends volunteer you into a game where you sum the shortest paths from classroom \(A\) to classroom \(B\) for each of the \(D\) days given these new constraints. Even more annoyingly, the school happens to shut down all classrooms connected to classroom \(A\) and \(B\) which are one layer below \(A\) and \(B\).

Given the layout of the school, the number of days for EQAO, and \(A\), \(B\) and \(L\) for each day, can you find the sum of the shortest paths for your friends?

The first line contains the integer \(N\), the number of classrooms in Dr. G.W. Williams.

The following \(N-1\) lines contain integers \(u\)_i and \(v\)_i, representing a hallway from classroom \(u\)_i to \(v\)_i

The next line contains the integer \(D\), the number of days of EQAO

The following \(D\) lines contain the integers \(A\)_i, \(B\)_i, and \(L\)_i, representing the two classrooms to find the shortest path between, and the layer which the temporary hallway is being built for day \(i\).

\(\{\text{1 } \leq N \leq 10^3 \}\)

\(\{\text{1 } \leq Q \leq 10^6 \}\)

For each of the \(D\) days, output how long it will take to get from classroom \(A\)_i to \(B\)_i in minutes on a new line.

As you may be able to tell, the school's solution to the travel problem is suboptimal (they tried their best), meaning that for some days of EQAO it is impossible to reach all classrooms. None of the inputs will contain these cases.

It will also be guaranteed classroom A is not directly under to classroom B and vice versa. For example, 1 is directly under 7.

Submit Solution