Subtask 1

Calculate the distance between ~2~ nodes using BFS or DFS. Calculate the distance travelled for every order of visiting the nodes and find the minimum.

Key Concepts Required: Graph Theory, Brute Force

Time Complexity: ~\mathcal{O}(N \cdot 2^D)~

Subtask 2

Precompute the distance between any two nodes by doing a DFS or BFS from each node.

If nodes ~a_1~ and ~b_1~ had bananas yesterday and nodes ~a_2~ and ~b_2~ had bananas today, you have four options today:

• ~a_1~ to ~a_2~ to ~b_2~
• ~a_1~ to ~b_2~ to ~a_2~
• ~b_1~ to ~a_2~ to ~b_2~
• ~b_1~ to ~b_2~ to ~a_2~

If ~dp[d][0] =~ distance travelled up to day ~d~ and ending on node ~a_2~, and ~dp[d][1]~ ending on node ~b_2~,

$$\displaystyle \begin{align*} dp[d][0] &= \min(dp[d-1][0] + dist[a_{d-1}][b_d], dp[d-1][1] + dist[b_d-1][b_d]) + dist[b_d][a_d] \\ dp[d][1] &= \min(dp[d-1][0] + dist[a_{d-1}][a_d], dp[d-1][1] + dist[b_d-1][a_d]) + dist[a_d][b_d] \end{align*}$$

And the answer is ~\min(dp[D][0], dp[D][1])~.

Because the monkey starts at node ~1~, ~dp[1][0] = dist[0][a_1], dp[1][1] = dist[0][b_1]~.

Key Concepts Required: Graph Theory, Dynamic Programming

Time Complexity: ~\mathcal{O}(N^2 + D)~

Subtask 3

This solution is similar to the solution to subtask 2. Instead of precomputing the distance between all pairs of nodes, we can find the distance between any two nodes by using their lowest common ancestor (LCA).

Key Concepts Required: Graph Theory, Dynamic Programming, Sparse Table

Time Complexity: ~\mathcal{O}(N + D)~