Assume that you have a tree and a list of guesses. Each guess says node is the parent of node if the tree is rooted at some node. Count how many root choices make at least guesses correct.
This is LeetCode , rated Hard.
The naive approach checks each of the possible roots separately. Too slow. You need to efficiently compute the answer for all roots. This is where rerooting DP comes in, and I'll walk you through it.