## Editorial for An Animal Contest 2 P6 - Koala Transport System

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Authors:

,#### Subtask 1

First, we run a DFS from node to build a array. Let be the next node on the path from to , and will store a dummy node, such as .

Let store the minimal distance from any node on the path to node . We can fill the array by running a multi-node BFS for every node . To do this, simply use the array and push the nodes from the path into the queue, and perform BFS normally.

Now, we can process the queries by setting each node as and summing the distance for all by using the array, and taking the minimum value after setting all nodes.

**Time Complexity**:

#### Subtask 2

To solve this subtask, we only need to run DFS for the single query.

We initialize an array to store the number of feeding grounds in the subtree of node . We can fill up this array by running a DFS from node .

We now make the observation that the best teleportation path sets as a leaf node. Why? Let's say that the best teleportation path does not set as a leaf node. We can make this teleportation path better by setting one of the children of as , let's call this child . This allows any feeding grounds in the subtree of closer access to a teleporter and decreases or maintains the total distance travelled from all feeding grounds to node .

Let represent the total distance travelled from all feeding grounds to node without the aid of any teleporters and represent some total distance travelled from all feeding grounds to node that can be achieved with the aid of teleporters. We note that is just subtracted by some distance .

Therefore, we will attempt to maximize .

We now run a DFS with an additional variable which stores the current sum of the distance that can be subtracted if we have teleporters from , where is the current node we are running DFS on. For all nodes in the subtree of , we set the node as a teleporter by simply increasing by the number of feeding grounds in the subtree of . This is because all feeding grounds in the subtree of now have less distance to travel to reach a teleporter. When we reach a leaf node, we simply set to .

We now run our last DFS which will get the total distance for all feeding grounds to node if there were no teleporters installed. To do this, keep a variable when running DFS to store the distance from the current node to node . Now, for all feeding grounds which we encounter during our DFS, we can simply add our variable to .

Our answer is simply .

Note that the last DFS can be merged for a faster runtime.

**Time Complexity**:

#### Subtask 3

Let's consider a set of candidate locations .

Suppose we consider the root as our candidate. Our answer would be the sum of the depths of the feeding locations.

Now suppose we have a different candidate location. How much do we save by moving the node from the root to such a location? Every time we "move in the direction of a feeding location", we save unit of time per feeding location. A good way to calculate this is for each feeding location, add to every node on the path from it to the root. In order to determine the amount of time we save, we can simply query the path sum of our node .

The final observation is similar to one noted in the previous subtask: leaves are always optimal. However, we see that choosing a feeding location is always at least as optimal as a leaf, since anything lower than the lowest feeding location is not more optimal.

Hence, we consider only the feeding locations as candidates. To implement path update and path query efficiently, we can use HLD with two BITs, although other solutions exist.

**Time Complexity**:

## Comments