DP on a tree (Tree DP)
DP on a tree is a class of problems where the values at a vertex are computed based on the values of its children in the DFS tree.
Tree diameter
Diameter — the length of the maximum simple path between two vertices of a tree.
Classic DP idea:
For each vertex we compute:
- — the maximum depth of a path downward (to any descendant)
Then a path passing through :