I am trying to understand the problem but still cannot understand it.
can anybody explain the problem along with the solution of CERSOL.
From Invitation to Alkhwarizm ā 2019 by IIIT Allahabad
Problem Setter ā fLUKEmASTER
This problem can be approached as a normal vertex cover problem on a binary tree with an extra restriction that nodes from all classes (1 to k ) should be considered .
This extra constraint can be handled by introducing an extra state in the naive solution for vertex cover of a binary tree.
This state could be a mask for all the classes which are to be found in the subtree of a node .
Hence, the final states could be dp(node)(mask)(parent).
To compute the value of a particular state, we need to divide the mask between the two children for the node .
The net complexity of the code would be lesser than O(nā22k).(Think why?)