Editorial for COCI '19 Contest 5 #4 Putovanje
Submitting an official solution before solving the problem yourself is a bannable offence.
Note that we really care about the number of times we need to traverse each of the roads. Once we know that, it is pretty easy to decide whether we will buy multiple single-pass tickets or a single multi-pass ticket.
In the first subtask, it was enough to use an algorithm like BFS or DFS to find a path between and
while increasing the counter of traversals for each edge.
In the second subtask, our tree is actually a chain. Let's think about that chain as an array. Let's also keep around another array called . Now, for every pair
and
we can increase
by
and decrease
by
where
denotes the position of node
in our chain. After we have done this for all neighbouring pairs, we can go over the
array and add its elements into some variable
. Note that in each moment of this traversal that variable holds the number of times we have traversed the corresponding edge in a chain.
To score all points we will slightly modify this algorithm to make it work on a tree. Let's root the tree in an arbitrary node. Let be the lowest common ancestor of
and
. Let's now increase
by
, increase
by
and decrease
by
. Now we can simply find out the number of traversals of each road by calculating the sum of
values in a subtree of that road.
There is an alternative solution of the same time complexity which uses the so-called small-to-large trick. You can read about a very similar idea on this link.
Comments