Editorial for DMOPC '17 Contest 3 P6 - Mimi and Scarf
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For the first subtask, call DFS from each node to find the longest valid path with
as an endpoint.
Time Complexity:
For the second subtask, note that the answer will always be the diameter unless the entire tree is a path and this path is invalid. Finding the diameter can be done in two DFS's (or BFS's if you want). If the diameter is the same as the number of nodes in the tree, then the entire tree is a path. (Alternatively, you can check if a tree is a path by looking at the degrees of each node, although for this subtask, you have to find the diameter anyways). Perform a DFS from one of the endpoints of the entire path to see if the entire path is a stripe or not. If the tree is not a path, or this path is not a stripe, then the answer is equal to the diameter. Otherwise, it is the diameter minus one.
Time Complexity:
For the third subtask, we use centroid decomposition to break down the tree. Let be an arbitrary node and consider its subtree (obtained from centroid decomposition). To merge paths
and
with endpoints at
and in its subtree, there are two cases:
Case 1: The node directly after in
has a different colour than the node directly after
in
.
Then and
can simply be merged. Define
to be the maximum length of any path going through a neighbour with colour
. To find the maximum length, find the largest two elements in
and take their sum minus one.
Case 2: The node directly after in
has the same colour as the node directly after
in
.
Consider an arbitrary path from
in its subtree. Call the length of the stripe beginning from
in this path
. Let
be the colour of the neighbour of
which
leads from.
Loop through each neighbour of . Let
be the current one.
For each value of , record the longest total length of a valid path going through
which obtained this value of
. Call this length
. For each value of
and value of
, record the longest total length of a valid path which passes through a neighbour which was DFSed before
and such that this path obtained these values of
and
. Call this length
.
DFS from to compute this
array. Do not update the
array. To merge paths of the same colour, for each length
, you must find the maximum of
. Once this is done, update
with the values in the
array. To maintain
, you can either use an RMQ Fenwick tree, or you can sort the neighbours based on the sizes of their subtrees and maintain the updates in linear time. Either way yields the same time complexity.
The final answer is the maximum length obtained over both these cases and over all nodes .
Time Complexity:
Comments