Query relating to TREEDGE

Do we have to go from u to v through their sub-trees or can we go from a parent node?

You can go any way. Your aim is to maximise the weighted path length. So choose whichever is greater.

If you consider going through their subtrees, you’ll have to add an edge to the end to one of the nodes in their subtree. You can choose this suitable node using dynamic programming.

Here is its editorial.

2 Likes
//