Basic Dp On Tree

   

 Problem: 

    Given a tree with n nodes we have to    find the number of nodes under each sub-tree

 The root is 1.

 Solution:

  

  we can solve this with dynamic programming

       

1. Determine the bottom nodes of the tree (with no children)
2. Assign "weight" 1 to each of the bottom nodes
3. Build your way up the tree calculating the "weight" of each node (for example a node with 2 children has "weight" 3)
4. That's your answer....

    Related Problem:

     Even-Tree

                Cut The Tree