Dado un número entero N , la tarea es construir un árbol tal que la suma de 
para todos los pares ordenados (u, v) sea el máximo donde u != v . Imprime la suma máxima posible.
Ejemplos:
Input: N = 4
Output: 26
1
/
2
/
3
/
4
For node 1, 1*2 + 1*2 + 1*1 = 5
For node 2, 2*1 + 2*2 + 2*1 = 8
For node 3, 2*1 + 2*2 + 2*1 = 8
For node 4, 1*1 + 1*2 + 1*2 = 5
Total sum = 5 + 8 + 8 + 5 = 26
Input: N = 6
Output: 82
Enfoque: Sabemos que la suma del grado de todos los Nodes en un árbol es (2 * N) – 2 donde N es el número de Nodes en el árbol. Como tenemos que maximizar la suma, tenemos que minimizar el número de Nodes hoja, ya que los Nodes hoja tienen el grado mínimo entre todos los Nodes del árbol y el árbol será de la forma:
1
/
2
/
...
/
N
donde solo el Node raíz y el único Node hoja tendrán grado 1 y todos los demás Nodes tendrán grado 2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// Function to return the maximum possible sum
ll maxSum(int N)
{
ll ans = 0;
for (int u = 1; u <= N; u++) {
for (int v = 1; v <= N; v++) {
if (u == v)
continue;
// Initialize degree for node u to 2
int degreeU = 2;
// If u is the leaf node or the root node
if (u == 1 || u == N)
degreeU = 1;
// Initialize degree for node v to 2
int degreeV = 2;
// If v is the leaf node or the root node
if (v == 1 || v == N)
degreeV = 1;
// Update the sum
ans += (degreeU * degreeV);
}
}
return ans;
}
// Driver code
int main()
{
int N = 6;
cout << maxSum(N);
}
Java
// Java implementation of above approach
class GFG
{
// Function to return the maximum possible sum
static int maxSum(int N)
{
int ans = 0;
for (int u = 1; u <= N; u++)
{
for (int v = 1; v <= N; v++)
{
if (u == v)
continue;
// Initialize degree for node u to 2
int degreeU = 2;
// If u is the leaf node or the root node
if (u == 1 || u == N)
degreeU = 1;
// Initialize degree for node v to 2
int degreeV = 2;
// If v is the leaf node or the root node
if (v == 1 || v == N)
degreeV = 1;
// Update the sum
ans += (degreeU * degreeV);
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 6;
System.out.println(maxSum(N));
}
}
// This code is contributed by Code_Mech
Python3
# Python3 implementation of above approach # Function to return the maximum possible sum def maxSum(N) : ans = 0; for u in range(1, N + 1) : for v in range(1, N + 1) : if (u == v) : continue; # Initialize degree for node u to 2 degreeU = 2; # If u is the leaf node or the root node if (u == 1 or u == N) : degreeU = 1; # Initialize degree for node v to 2 degreeV = 2; # If v is the leaf node or the root node if (v == 1 or v == N) : degreeV = 1; # Update the sum ans += (degreeU * degreeV); return ans; # Driver code if __name__ == "__main__" : N = 6; print(maxSum(N)); # This code is contributed by Ryuga
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to return the maximum possible sum
static int maxSum(int N)
{
int ans = 0;
for (int u = 1; u <= N; u++)
{
for (int v = 1; v <= N; v++)
{
if (u == v)
continue;
// Initialize degree for node u to 2
int degreeU = 2;
// If u is the leaf node or the root node
if (u == 1 || u == N)
degreeU = 1;
// Initialize degree for node v to 2
int degreeV = 2;
// If v is the leaf node or the root node
if (v == 1 || v == N)
degreeV = 1;
// Update the sum
ans += (degreeU * degreeV);
}
}
return ans;
}
// Driver code
static void Main()
{
int N = 6;
Console.WriteLine(maxSum(N));
}
}
// This code is contributed by Chandan_jnu
PHP
<?php
// PHP implementation of above approach
// Function to return the maximum
// possible sum
function maxSum($N)
{
$ans = 0;
for ($u = 1; $u <= $N; $u++)
{
for ($v = 1; $v <= $N; $v++)
{
if ($u == $v)
continue;
// Initialize degree for node u to 2
$degreeU = 2;
// If u is the leaf node or the
// root node
if ($u == 1 || $u == $N)
$degreeU = 1;
// Initialize degree for node v to 2
$degreeV = 2;
// If v is the leaf node or the
// root node
if ($v == 1 || $v == $N)
$degreeV = 1;
// Update the sum
$ans += ($degreeU * $degreeV);
}
}
return $ans;
}
// Driver code
$N = 6;
echo maxSum($N);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript implementation of above approach
// Function to return the maximum possible sum
function maxSum(N)
{
var ans = 0;
for (var u = 1; u <= N; u++) {
for (var v = 1; v <= N; v++) {
if (u == v)
continue;
// Initialize degree for node u to 2
var degreeU = 2;
// If u is the leaf node or the root node
if (u == 1 || u == N)
degreeU = 1;
// Initialize degree for node v to 2
var degreeV = 2;
// If v is the leaf node or the root node
if (v == 1 || v == N)
degreeV = 1;
// Update the sum
ans += (degreeU * degreeV);
}
}
return ans;
}
// Driver code
var N = 6;
document.write( maxSum(N));
</script>
Producción:
82
Complejidad del tiempo: O(N 2 )
Espacio Auxiliar: O(1)