For all subtasks, it is always optimal to pick a junction that has the most number of apples between it and the root.

Subtask 1

For each friend, we will go through all the junctions, and follow the parent junction until we reach the root, and count the number of apples on that path. We will then select the junction that had the most number of apples, and mark those junctions on the path to the root to become "inactive" for ~K~ minutes.

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

Subtask 2

For the second subtask, we can find the junction with the maximum number of apples from the root, by performing a depth first search from the root junction. Once again, we will have to mark the junctions on the path to the root to become inactive for ~K~ minutes. We will do this for each friend.

Time Complexity: ~\mathcal{O}(N \cdot M)~

Subtask 3

For the third subtask, a key observation is that the ~i^\text{th}~ friend will take the same path as the ~(i + K)^\text{th}~ friend. In addition, the junction selected by each path will always be a leaf (unless there are no apples currently on the tree). To determine the order of the leaves, we can do a depth first search from the root, to determine the depth of each leaf. From there, we can go through the leaves in non-increasing order of depth and follow the parent and mark the junctions as visited, until we reach a vertex that has already been visited. From here, we know that all other vertices on the path to the root have been visited. The order of leaves can be determined by selecting the ~K~ largest leaves in order, based on the number of vertices it visited for the first time on the path to the root (which can be done in linear time in counting sort, though this was not required). Now, we can determine the answer for each friend.

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