Editorial for DMOPC '17 Contest 3 P6 - Mimi and Scarf

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: r3mark

For the first subtask, call DFS from each node $i$ ~i~ to find the longest valid path with $i$ ~i~ as an endpoint.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

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: $\mathcal O(N)$ ~\mathcal O(N)~

For the third subtask, we use centroid decomposition to break down the tree. Let $i$ ~i~ be an arbitrary node and consider its subtree (obtained from centroid decomposition). To merge paths $P_1$ ~P_1~ and $P_2$ ~P_2~ with endpoints at $i$ ~i~ and in its subtree, there are two cases:

Case 1: The node directly after $i$ ~i~ in $P_1$ ~P_1~ has a different colour than the node directly after $i$ ~i~ in $P_2$ ~P_2~.

Then $P_1$ ~P_1~ and $P_2$ ~P_2~ can simply be merged. Define $S[C]$ ~S[C]~ to be the maximum length of any path going through a neighbour with colour $C$ ~C~. To find the maximum length, find the largest two elements in $S$ ~S~ and take their sum minus one.

Case 2: The node directly after $i$ ~i~ in $P_1$ ~P_1~ has the same colour as the node directly after $i$ ~i~ in $P_2$ ~P_2~.

Consider an arbitrary path $P$ ~P~ from $i$ ~i~ in its subtree. Call the length of the stripe beginning from $i$ ~i~ in this path $L$ ~L~. Let $C$ ~C~ be the colour of the neighbour of $i$ ~i~ which $P$ ~P~ leads from.

Loop through each neighbour of $i$ ~i~. Let $j$ ~j~ be the current one.

For each value of $L$ ~L~, record the longest total length of a valid path going through $j$ ~j~ which obtained this value of $L$ ~L~. Call this length $T[L]$ ~T[L]~. For each value of $L$ ~L~ and value of $C$ ~C~, record the longest total length of a valid path which passes through a neighbour which was DFSed before $j$ ~j~ and such that this path obtained these values of $L$ ~L~ and $C$ ~C~. Call this length $M[C][L]$ ~M[C][L]~.

DFS from $j$ ~j~ to compute this $T$ ~T~ array. Do not update the $M$ ~M~ array. To merge paths of the same colour, for each length $L$ ~L~, you must find the maximum of $T[L]+M[c_j][K-L]$ ~T[L]+M[c_j][K-L]~. Once this is done, update $M[c_j]$ ~M[c_j]~ with the values in the $T$ ~T~ array. To maintain $M$ ~M~, 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 $i$ ~i~.

Time Complexity: $\mathcal O(N \log^2 N)$ ~\mathcal O(N \log^2 N)~

Comments

There are no comments at the moment.