Maximize the sum of products of the degrees between any two vertices of the tree | Function to return the maximum possible sum ; Initialize degree for node u to 2 ; If u is the leaf node or the root node ; Initialize degree for node v to 2 ; If v is the leaf node or the root node ; Update the sum ; Driver code
< ? php function maxSum ( $ N ) { $ ans = 0 ; for ( $ u = 1 ; $ u <= $ N ; $ u ++ ) { for ( $ v = 1 ; $ v <= $ N ; $ v ++ ) { if ( $ u == $ v ) continue ; $ degreeU = 2 ; if ( $ u == 1 $ u == $ N ) $ degreeU = 1 ; $ degreeV = 2 ; if ( $ v == 1 $ v == $ N ) $ degreeV = 1 ; $ ans += ( $ degreeU * $ degreeV ) ; } } return $ ans ; } $ N = 6 ; echo maxSum ( $ N ) ; ? >