Halo,
Its 4AM here and i cant sleep so i brought you a nice trick and couple of problems to practice it.
Introduction
(Our dp changes if we change root of the tree, otherwise it wont make any sens to use this trick)
Lets say we want to find $$$dp_v$$$ for every vertex in a tree, this dp must be updated using the children of vertex $$$v$$$. Then the trick allows you to move the root from a vertex to one of it's adjacent vertices in $$$O(1)$$$.
It will be much better if the problem wants you to move the root to all vertices.
Implementation
First calculate dp for a random root $$$rat$$$. Its obvious that if we change root $$$r$$$ to one of its adjacent vertex $$$v$$$, then only $$$dp_r$$$ and $$$dp_v$$$ can change, so that we can update $$$dp_r$$$ using its new children and also $$$dp_v$$$ can be updated the same way.
Now being able to move the root with distance one, we will run a dfs from $$$rat$$$, and move the root with dfs.
See the semi-code below :
Applications
It will be added soon including a fairly complete solution using this trick for every application, its about 5:15 AM here :).
thanks for your attention.