DP on Trees | Set | C ++ program to find diameter of a tree using DFS . ; Function to find the diameter of the tree using Dynamic Programming ; Store the first maximum and secondmax ; Traverse for all children of node ; Call DFS function again ; Find first max ; Secondmaximum ; else if ( dp1 [ * i ] > secondmax ) Find secondmaximum ; Base case for every node ; if ( firstmax != - 1 ) Add ; Find dp [ 2 ] ; Return maximum of both ; Driver Code ; Constructed tree is 1 / \ 2 3 / \ 4 5 ; create undirected edges ; Find diameter by calling function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int diameter = -1 ; int dfs ( int node , int parent , int dp1 [ ] , int dp2 [ ] , list < int > * adj ) { int firstmax = -1 ; int secondmax = -1 ; for ( auto i = adj [ node ] . begin ( ) ; i != adj [ node ] . end ( ) ; ++ i ) { if ( * i == parent ) continue ; dfs ( * i , node , dp1 , dp2 , adj ) ; if ( firstmax == -1 ) { firstmax = dp1 [ * i ] ; } else if ( dp1 [ * i ] >= firstmax ) { secondmax = firstmax ; firstmax = dp1 [ * i ] ; } { secondmax = dp1 [ * i ] ; } } dp1 [ node ] = 1 ; dp1 [ node ] += firstmax ; if ( secondmax != -1 ) dp2 [ node ] = 1 + firstmax + secondmax ; return max ( dp1 [ node ] , dp2 [ node ] ) ; } int main ( ) { int n = 5 ; list < int > * adj = new list < int > [ n + 1 ] ; adj [ 1 ] . push_back ( 2 ) ; adj [ 2 ] . push_back ( 1 ) ; adj [ 1 ] . push_back ( 3 ) ; adj [ 3 ] . push_back ( 1 ) ; adj [ 2 ] . push_back ( 4 ) ; adj [ 4 ] . push_back ( 2 ) ; adj [ 2 ] . push_back ( 5 ) ; adj [ 5 ] . push_back ( 2 ) ; int dp1 [ n + 1 ] , dp2 [ n + 1 ] ; memset ( dp1 , 0 , sizeof dp1 ) ; memset ( dp2 , 0 , sizeof dp2 ) ; cout << " Diameter ▁ of ▁ the ▁ given ▁ tree ▁ is ▁ " << dfs ( 1 , 1 , dp1 , dp2 , adj ) << endl ; return 0 ; }