Let ~X, Y, Z~ be the nodes with Josh, Nils, and Mike are at respectively. Let ~A~ be the selected building which minimises the sum of distances.

Subtask 1

The crucial observation is that ~A~ is the median of ~X~, ~Y~ and ~Z~. This means we can use combinatorics to calculate the number of combinations for each value of ~A~. There are three cases:

• ~X~, ~Y~ and ~Z~ are all equal to ~A~: there is one scenario in this case.
• Exactly two of ~X~, ~Y~, and ~Z~ are equal to ~A~: there are ~3(N-1)~ scenarios in this case, as there are ~N-1~ positions other than ~A~ that can be chosen, and ~3~ ways to allocate Josh, Nils and Mike to the positions.
• All three of ~X~, ~Y~ and ~Z~ are distinct: there are ~6(A-1)(N-A)~ scenarios in this case, as there are ~(A-1)~ ways to choose which position is to the left of ~A~, ~(N-A)~ ways to choose which position is to the right of ~A~, and ~6~ ways to allocate Josh, Nils and Mike to these positions.

Hence, the answer for the building ~A~ is ~3(N-1) + 6(A-1)(N-A) + 1~.

Time complexity: ~\mathcal{O}(N)~

Subtask 2

We can brute force over all ~\mathcal{O}(N^3)~ values of ~X~, ~Y~ and ~Z~. For each combination, we can find the optimal building in ~\mathcal{O}(N)~ time, by performing a DFS / BFS from ~X, Y, Z~. We can alternatively precompute the distances between all buildings by performing DFS, BFS, or Floyd-Warshall.

Time complexity: ~\mathcal{O}(N^4)~

Subtask 3

Root the tree arbitrarily. If we consider the list ~[LCA(X, Y), LCA(X, Z), LCA(Y, Z)]~, where ~LCA(a, b)~ is the lowest common ancestor of ~a~ and ~b~, it can be seen that ~A~ equals the least frequently occurring element in this list. The proof of this is left as an exercise to the reader.

This allows us to find the optimal building for each combination in ~\mathcal{O}(1)~ time. Note that it may be easier and faster to precompute the LCA between all pairs of buildings.

Time complexity: ~\mathcal{O}(N^3)~

Subtask 4

There are multiple solutions, one of which will be described below.

Let ~f(V)~ be the number of combinations where the optimal building lies in the subtree of ~X~. Note that our observation from subtask ~3~ implies that ~A~ lies in the subtree of ~V~ if and only if at least two of ~X~, ~Y~ and ~Z~ lie in the subtree of ~V~.

Hence, ~f(V) = sz(V)^3 + 3sz(V)^2(N-sz(V))~, where ~sz(V)~ is the size of the subtree of ~V~.

Then, the answer to the problem for each building ~A~ is the difference between ~f(A)~, and the sum of all ~f(B)~ where ~B~ is a child of ~A~.

Time complexity: ~\mathcal{O}(N)~