During the second day of this year's Balkan Olympiad in Informatics held in Greece there was a problem on implementing Alien's trick from IOI 2016 — Aliens but on trees. Link to the problem.. Shortly the problem askes us to choose $$$K$$$ edges from the tree of $$$N$$$ nodes, such that none of the chosen edges share a common node or report that this is not possible for the given tree. Both $$$N$$$ and $$$K$$$ are up to $$$10^6$$$.

I got a solution in $$$O(N \cdot K)$$$, however I couldn't optimize it further until I was told that it requires implementation of the Alien's trick. Since I haven't used this trick before, I'm not sure on how to use the cost function here. Do we still need two DP tables, and how to merge with the children, how do we keep track on how many edges we have picked in solution with the current cost, how are we sure whether exactly $$$K$$$ edges are taken or less.