Editorial for DMOPC '21 Contest 3 P5 - Crowded Travels

Remember to use this editorial 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: TechnobladeNeverDies

Subtask 1

Let E_u be the minimum expected time to reach node 1 from node u, where E_1=0.

Observe that if the tree is rooted at 1, when in an uncrowded node, you must move towards the parent as you must pass through the parent on the route to 1; that is, for an uncrowded node u we have E_u=w_u+E_{f_u}, where f_u is the father of u and w_u is the weight of the edge between u and f_u.

On the other hand, in a crowded node you cannot control where the next step is, so E_u=\frac{1}{k_u}\left[(w_u+E_{f_u})+\sum\limits_{ch}(w_{ch}+E_{ch})\right] where ch sums over all children of u, and k_u is the number of neighbors of u.

We claim that for all nodes E_u we can express it as a_u+b_uE_{f_u} for rational a_u and b_u. It is trivial to prove this inductively; for a leaf or uncrowded node we have a_u=w_u and b_u=1, and for a crowded node we have

\displaystyle \begin{align*}
E_u &= \frac{1}{k_u}\left[(w_u+E_{f_u})+\sum_{ch}(w_{ch}+E_{ch})\right] \\
E_u &= \frac{1}{k_u}\left[(w_u+E_{f_u})+\sum_{ch}(w_{ch}+a_{ch}+b_{ch}E_u)\right] \\
\left(1-\frac{1}{k_u}\sum_{ch}b_{ch}\right)E_u &= \frac{w_u+\sum_{ch}(w_{ch}+a_{ch})}{k_u}+\frac{1}{k_u}E_{f_u}

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

Time Complexity: \mathcal{O}(n + q)

Subtask 2

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

\displaystyle \begin{align*}
\frac{1}{k_u}E_u &= \frac{w_u+\sum_{ch}(w_{ch}+a_{ch})}{k_u}+\frac{1}{k_u}E_{f_u} \\
E_u &= w_u+\sum_{ch}(w_{ch}+a_{ch})+E_{f_u}

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

\displaystyle a_u=\begin{cases}w_u&\text{uncrowded}\\w_u+\sum\limits_{ch}(w_{ch}+a_{ch})&\text{crowded}\end{cases}

Consider maintaining a_u for each node with HLD. As we modify the value of a_u for a node, we have to update all ancestors of u 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: \mathcal{O}(n\log n+q\log^2n) using HLD, or \mathcal{O}((n+q)\log n) with LCT.


There are no comments at the moment.