In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit.

Say that we are given a rooted tree so that any element in the tree has a profit. An independent set in the tree is a collection of vertices no two of which are a parent and a child. The goal is to find an independent set of maximum profits. Is your solution an example of divide and conqueror dynamic programming? Hint: Think on a solution with the root and solution without the root.