Cuente pares de Nodes que tengan una distancia mínima entre ellos igual a la diferencia de sus distancias desde la raíz

Dado un árbol N-ario que consta de N Nodes valorados de [1, N] , donde el Node 1 es la raíz, la tarea es contar los pares de Nodes que tienen una distancia mínima entre ellos igual a la diferencia entre las distancias de ambos Nodes de la raíz

Ejemplos:

Entrada: N = 3, Edges[][] = {{1, 2}, {1, 3}}, Abajo está el árbol:
                        1
                      / \
                   2 3
Salida: 5   
Explicación:  Los siguientes pares satisfacen las condiciones: {( 1, 1), (2, 2), (3, 3), (2, 1), (3, 1)}.

Entrada: N = 4, Edges[][] = {{1, 2}, {1, 3}, {2, 4}}, Abajo está el árbol:
                     1
                   / \
                2 3
               |
             4
Salida: 8 

Enfoque ingenuo: el enfoque más simple es encontrar la distancia entre todos los pares posibles (i, j) y verificar para cada par de Nodes (i, j) , si distancia (i, j) = distancia (1, i) – distancia ( 1, j) o no mediante el uso de búsqueda transversal en profundidad . 
Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

La distancia mínima desde el Node X y el ancestro del Node X satisface los criterios anteriores. Por tanto, la tarea se reduce a encontrar todos los ancestros de cada Node del árbol .

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans , para almacenar el recuento de pares de Nodes.
• Realice un recorrido DFS desde el Node raíz con los argumentos Node actual , Node principal y profundidad del Node hasta el Node actual.
• Realice recursivamente DFS Traversal en el Node secundario de cada Node con el Node actual como Node principal y la profundidad aumentada en 1 .
• En cada llamada, agregue la profundidad del Node actual a la variable ans .
• Después de completar los pasos anteriores, imprima el valor de ans como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Stores the count of pairs
long long ans = 0;
 
// Store the adjacency list of
// the connecting vertex
vector<int> adj[int(1e5) + 1];
 
// Function for theto perform DFS
// traversal of the given tree
void dfsUtil(int u, int par, int depth)
{
    // Traverse the adjacency list
    // of the current node u
    for (auto it : adj[u]) {
 
        // If the current node
        // is the parent node
        if (it != par) {
            dfsUtil(it, u, depth + 1);
        }
    }
 
    // Add number of ancestors, which
    // is same as depth of the node
    ans += depth;
}
 
// Function for DFS traversal of
// the given tree
void dfs(int u, int par, int depth)
{
    dfsUtil(u, par, depth);
 
    // Print the result
    cout << ans << endl;
}
 
// Function to find the count of pairs
// such that the minimum distance
// between them is equal to the difference
// between distance of the nodes from root node
void countPairs(vector<vector<int> > edges)
{
    for (int i = 0; i < edges.size(); i++) {
 
        int u = edges[i][0];
        int v = edges[i][1];
 
        // Add edges to adj[]
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    dfs(1, 1, 1);
}
 
// Driver Code
int main()
{
    vector<vector<int> > edges
        = { { 1, 2 }, { 1, 3 }, { 2, 4 } };
 
    countPairs(edges);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Stores the count of pairs
static int ans = 0;
 
// Store the adjacency list of
// the connecting vertex
static ArrayList<Integer> []adj = new ArrayList[(int)(1e5) + 1];
static{
    for(int i = 0; i < adj.length; i++)
        adj[i] = new ArrayList<>();
}
   
// Function for theto perform DFS
// traversal of the given tree
static void dfsUtil(int u, int par, int depth)
{
   
    // Traverse the adjacency list
    // of the current node u
    for (int it : adj[u]) {
 
        // If the current node
        // is the parent node
        if (it != par) {
            dfsUtil(it, u, depth + 1);
        }
    }
 
    // Add number of ancestors, which
    // is same as depth of the node
    ans += depth;
}
 
// Function for DFS traversal of
// the given tree
static void dfs(int u, int par, int depth)
{
    dfsUtil(u, par, depth);
 
    // Print the result
    System.out.print(ans +"\n");
}
 
// Function to find the count of pairs
// such that the minimum distance
// between them is equal to the difference
// between distance of the nodes from root node
static void countPairs(int [][]edges)
{
    for (int i = 0; i < edges.length; i++) {
 
        int u = edges[i][0];
        int v = edges[i][1];
 
        // Add edges to adj[]
        adj[u].add(v);
        adj[v].add(u);
    }
 
    dfs(1, 1, 1);
}
 
// Driver Code
public static void main(String[] args)
{
    int [][]edges
        = { { 1, 2 }, { 1, 3 }, { 2, 4 } };
 
    countPairs(edges);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for the above approach
 
# Stores the count of pairs
ans = 0
 
# Store the adjacency list of
# the connecting vertex
adj = [[] for i in range(10**5+1)]
 
# Function for theto perform DFS
# traversal of the given tree
def dfsUtil(u, par, depth):
    global adj, ans
     
    # Traverse the adjacency list
    # of the current node u
    for it in adj[u]:
 
        # If the current node
        # is the parent node
        if (it != par):
            dfsUtil(it, u, depth + 1)
 
    # Add number of ancestors, which
    # is same as depth of the node
    ans += depth
 
# Function for DFS traversal of
# the given tree
def dfs(u, par, depth):
    global ans
    dfsUtil(u, par, depth)
     
    # Print result
    print (ans)
 
# Function to find the count of pairs
# such that the minimum distance
# between them is equal to the difference
# between distance of the nodes from root node
def countPairs(edges):
    global adj
    for i in range(len(edges)):
        u = edges[i][0]
        v = edges[i][1]
 
        # Add edges to adj[]
        adj[u].append(v)
        adj[v].append(u)
    dfs(1, 1, 1)
 
# Driver Code
if __name__ == '__main__':
    edges = [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ] ]
 
    countPairs(edges)
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
 
// Stores the count of pairs
static int ans = 0;
 
// Store the adjacency list of
// the connecting vertex
static List<int> []adj = new List<int>[(int)(1e5) + 1];
   
// Function for theto perform DFS
// traversal of the given tree
static void dfsUtil(int u, int par, int depth)
{
   
    // Traverse the adjacency list
    // of the current node u
    foreach (int it in adj[u]) {
 
        // If the current node
        // is the parent node
        if (it != par) {
            dfsUtil(it, u, depth + 1);
        }
    }
 
    // Add number of ancestors, which
    // is same as depth of the node
    ans += depth;
}
 
// Function for DFS traversal of
// the given tree
static void dfs(int u, int par, int depth)
{
    dfsUtil(u, par, depth);
 
    // Print the result
    Console.Write(ans +"\n");
}
 
// Function to find the count of pairs
// such that the minimum distance
// between them is equal to the difference
// between distance of the nodes from root node
static void countPairs(int [,]edges)
{
    for (int i = 0; i < edges.GetLength(0); i++)
    {
 
        int u = edges[i,0];
        int v = edges[i,1];
 
        // Add edges to []adj
        adj[u].Add(v);
        adj[v].Add(u);
    }
 
    dfs(1, 1, 1);
}
 
// Driver Code
public static void Main(String[] args)
{
    int [,]edges
        = { { 1, 2 }, { 1, 3 }, { 2, 4 } };
 
    for(int i = 0; i < adj.GetLength(0); i++)
        adj[i] = new List<int>();
    countPairs(edges);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program for the above approach
 
// Stores the count of pairs
var ans = 0;
 
// Store the adjacency list of
// the connecting vertex
var adj = Array.from(Array(100001), ()=>Array());
 
// Function for theto perform DFS
// traversal of the given tree
function dfsUtil(u, par, depth)
{
    // Traverse the adjacency list
    // of the current node u
    adj[u].forEach(it => {
         
 
        // If the current node
        // is the parent node
        if (it != par) {
            dfsUtil(it, u, depth + 1);
        }
    });
 
    // Add number of ancestors, which
    // is same as depth of the node
    ans += depth;
}
 
// Function for DFS traversal of
// the given tree
function dfs(u, par, depth)
{
    dfsUtil(u, par, depth);
 
    // Print the result
    document.write( ans + "<br>");
}
 
// Function to find the count of pairs
// such that the minimum distance
// between them is equal to the difference
// between distance of the nodes from root node
function countPairs(edges)
{
    for (var i = 0; i < edges.length; i++) {
 
        var u = edges[i][0];
        var v = edges[i][1];
 
        // Add edges to adj[]
        adj[u].push(v);
        adj[v].push(u);
    }
 
    dfs(1, 1, 1);
}
 
// Driver Code
var edges
    = [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ] ];
countPairs(edges);
 
// This code is contributed by itsok.
</script>

8

Complejidad temporal: O(N)
Espacio auxiliar: O(N)