Tree DP and Rerooting
Root the tree, compute each vertex from its children, then reuse those answers to get the result for every possible root in linear time.
The problem
A tree is a connected graph with no cycles: n vertices and n - 1 edges. Pick any vertex as the root and every other vertex gets a parent (the neighbour toward the root) and possibly children. The subtree of v is v and everything below it.
Subtrees overlap in a very clean way: the subtree of v is made of v plus the subtrees of its children, with no sharing between siblings. That is the structure DP wants, so most tree problems become: "compute dp[v] from dp[child] for every child".
1 of 6