The repository that contains all solutions made for the course Competitive Programming and Contests by the University of Pisa
Solved | Solution | Time |
---|---|---|
Dynamic Programming | 0.06 ms |
The solution to this problem uses the Dynamic Programming and the DFS visit over the Tree.
In addition, the dynamic programming uses the memorization technique where the algorithm memorizes all the node taken.
In addition, if the algorithm chooses the father, it can also take the children, if the algorithm doesn’t take the father it
can choose if take the children with the formula std::min(dp_mem[0][next], dp_mem[1][next])
.
The time and space complexity of the solution is O(V) where V is the number of vertices.