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

	#include<bits/stdc++.h>
	using namespace std;
	vector < int > v[105];
	bool visited[105];
	int c[105];
	int dfs( int x , int par){
	visited[x]=true;
	if(v[x].size()==1 && v[x][0]==par){ ///is leaf node
	return c[x];
	}
	bool s = false;
	for(int i=0;i<v[x].size();i++){
	int xx = v[x][i];
	if(visited[xx]==false){ /// not parent
	int re = dfs(xx,x); /// get the number of all nodes under xx
	if(re!=0){
	c[x]=c[x]+re;
	s=true;
	}
	}
	}
	if(s==true){
	return c[x];
	}
	else return 0;
	}
	int main(){
	int n, m,a,b;
	cin >> n >> m;
	for( int i = 0; i < m; i++ ){
	cin >> a >> b ;
	v[a].push_back( b );
	v[b].push_back( a );
	}
	for(int i=1;i<=n;i++){
	c[i] = 1;
	}
	int k = dfs(1,0);
	k = 0;
	for(int i=1;i<=n;i++){
	cout<<c[i]-1<<"\n";
	}
	return 0;
	}

view raw dp_tree.cpp hosted with ❤ by GitHub

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