## Editorial for DMOPC '21 Contest 3 P5 - Crowded Travels

**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.**

Author:

#### Subtask 1

Let be the minimum expected time to reach node from node , where .

Observe that if the tree is rooted at , when in an uncrowded node, you must move towards the parent as you must pass through the parent on the route to ; that is, for an uncrowded node we have , where is the father of and is the weight of the edge between and .

On the other hand, in a crowded node you cannot control where the next step is, so where sums over all children of , and is the number of neighbors of .

We claim that for all nodes we can express it as for rational and . It is trivial to prove this inductively; for a leaf or uncrowded node we have and , and for a crowded node we have

For the first subtask, we can directly use this to calculate , , and for every node.

**Time Complexity:**

#### Subtask 2

We claim that for every non-root node, . We also prove this inductively; for a leaf and uncrowded node this holds, and for a crowded node there are children, each of which have by the inductive hypothesis; hence the recurrence that we established above becomes

In other words, is the sum of over all ancestors of , where

Consider maintaining for each node with HLD. As we modify the value of for a node, we have to update all ancestors of in the current connected component formed by crowded nodes; if we can maintain this connected component with a DSU this becomes a classic path-add path-sum query problem.

**Time Complexity:** using HLD, or with LCT.

## Comments