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

Degree Of Node

    

    The degree of a vertex V in a graph is defined as the number of graph edges that touches the vertex V.

     

    In a graph,

        the total sum of all degree of

       vertex = 2 * E    [E = number of edge]

    For a Tree,

        the total sum of all degree of

       vertex = 2 * E

              = 2 * (n-1)

 So if the sum of all degree of 

  vertex = 2*(n-1) then it must be a tree

    Related Problem:

         Monk at the Graph Factory