Editorial for DMOPC '21 Contest 3 P5 - Crowded Travels
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