Número de árboles cuya suma de grados de todos los vértices es L

Dado un entero L que es la suma de grados de todos los vértices de algún árbol. La tarea es encontrar el recuento de todos esos árboles distintos (árboles etiquetados). Dos árboles son distintos si tienen al menos una sola arista diferente.
Ejemplos: 
 

Entrada: L = 2 
Salida: 1
Entrada: L = 6 
Salida: 16 
 

Solución simple : una solución simple es encontrar el número de Nodes del árbol que tiene la suma de los grados de todos los vértices como L. El número de Nodes en dicho árbol es n = (L / 2 + 1) como se describe en este artículo. 
Ahora la solución es formar todos los árboles etiquetados que se pueden formar usando n Nodes. Este enfoque es bastante complejo y para valores más grandes de n no es posible averiguar el número de árboles usando este proceso.
Solución eficiente : una solución eficiente es encontrar el número de Nodes usando la fórmula de Cayley que establece que hay n ^{(n – 2)} árboles con n vértices etiquetados. Entonces, la complejidad temporal del código ahora se reduce a O(n)que se puede reducir aún más a O (logn) usando exponenciación modular.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <iostream>
using namespace std;
#define ll long long int
 
// Iterative Function to calculate (x^y) in O(log y)
ll power(int x, ll y)
{
 
    // Initialize result
    ll res = 1;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x);
 
        // y must be even now
        // y = y / 2
        y = y >> 1;
        x = (x * x);
    }
    return res;
}
 
// Function to return the count
// of required trees
ll solve(int L)
{
    // number of nodes
    int n = L / 2 + 1;
 
    ll ans = power(n, n - 2);
 
    // Return the result
    return ans;
}
 
// Driver code
int main()
{
    int L = 6;
 
    cout << solve(L);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
// Iterative Function to calculate (x^y) in O(log y)
static long power(int x, long y)
{
 
    // Initialize result
    long res = 1;
 
    while (y > 0)
    {
 
        // If y is odd, multiply x with result
        if (y==1)
            res = (res * x);
 
        // y must be even now
        // y = y / 2
        y = y >> 1;
        x = (x * x);
    }
    return res;
}
 
// Function to return the count
// of required trees
static long solve(int L)
{
    // number of nodes
    int n = L / 2 + 1;
 
    long ans = power(n, n - 2);
 
    // Return the result
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
 
    int L = 6;
    System.out.println (solve(L));
}
}
 
// This code is contributed by ajit.

     
# Python implementation of the approach
 
# Iterative Function to calculate (x^y) in O(log y)
def power(x, y):
 
    # Initialize result
    res = 1;
 
    while (y > 0):
 
        # If y is odd, multiply x with result
        if (y %2== 1):
            res = (res * x);
 
        # y must be even now
        #y = y / 2
        y = int(y) >> 1;
        x = (x * x);
    return res;
 
 
# Function to return the count
# of required trees
def solve(L):
     
    # number of nodes
    n = L / 2 + 1;
 
    ans = power(n, n - 2);
 
    # Return the result
    return int(ans);
 
L = 6;
print(solve(L));
 
# This code has been contributed by 29AjayKumar

// C# implementation of the approach
using System;
 
class GFG
{
     
// Iterative Function to calculate (x^y) in O(log y)
static long power(int x, long y)
{
 
    // Initialize result
    long res = 1;
 
    while (y > 0)
    {
 
        // If y is odd, multiply x with result
        if (y == 1)
            res = (res * x);
 
        // y must be even now
        // y = y / 2
        y = y >> 1;
        x = (x * x);
    }
    return res;
}
 
// Function to return the count
// of required trees
static long solve(int L)
{
    // number of nodes
    int n = L / 2 + 1;
 
    long ans = power(n, n - 2);
 
    // Return the result
    return ans;
}
 
// Driver code
static public void Main ()
{
    int L = 6;
    Console.WriteLine(solve(L));
}
}
 
// This code is contributed by Tushil.

<script>
 
// Javascript implementation of the approach
 
// Iterative Function to calculate (x^y) in O(log y)
function power(x, y)
{
 
    // Initialize result
    var res = 1;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x);
 
        // y must be even now
        // y = y / 2
        y = y >> 1;
        x = (x * x);
    }
    return res;
}
 
// Function to return the count
// of required trees
function solve(L)
{
    // number of nodes
    var n = L / 2 + 1;
 
    var ans = power(n, n - 2);
 
    // Return the result
    return ans;
}
 
// Driver code
var L = 6;
document.write( solve(L));
 
// This code is contributed by rutvik_56.
</script>

16

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)