Problem - Possible Root Nodes

Assume that you have a tree and a list of guesses. Each guess says node $a$ is the parent of node $b$ if the tree is rooted at some node. Count how many root choices make at least $k$ guesses correct.

This is LeetCode $2581$, rated Hard.

The naive approach checks each of the $n$ possible roots separately. Too slow. You need to efficiently compute the answer for all $n$ roots. This is where rerooting DP comes in, and I'll walk you through it.