Recuento de ancestros con menor valor para cada Node de un árbol N-ario

Dado un árbol N-ario que consta de N Nodes con valores de 1 a N enraizados en 1, para todos los Nodes, imprima el número de ancestros que tienen un valor menor que el Node actual.

Ejemplo: 

   Entrada: A continuación se muestra el árbol dado:

                     1
                  / \
                4 5
              / / | \
            6 3 2 7                           

   Salida: 0 1 1 1 1 2 2   
   Explicación:  
   Dado que el Node 1 es el Node raíz, no tiene ancestros.
   Ancestros del Node 2: {1, 5}. El número de antepasados ​​que tienen un valor menor que 2 es 1.
   Antepasados ​​del Node 3: {1, 5}. El número de antepasados ​​que tienen un valor menor que 3 es 1.
   Antepasados ​​del Node 4: {1}. El número de antepasados ​​que tienen un valor menor que 4 es 1.
   Antepasados ​​del Node 5: {1}. El número de antepasados ​​que tienen un valor menor que 5 es 1.
   Antepasados ​​del Node 6: {1, 4}. El número de antepasados ​​que tienen un valor menor que 6 es 2.
   Antepasados ​​del Node 7: {1, 5}. El número de antepasados ​​que tienen un valor menor que 7 es 2

   Entrada: A continuación se muestra el árbol dado:

                   1
                  / \
                3 2
                      \
                       4    

   Salida: 0 1 1 2      
   Explicación:  
   el Node 1 no tiene ancestros.
   Ancestros del Node 2: {1}. El número de antepasados ​​que tienen un valor menor que 2 es 1.
   Antepasados ​​del Node 3: {1}. El número de antepasados ​​que tienen un valor menor que 3 es 1.

Enfoque de fuerza bruta: la idea es similar a lo que se menciona aquí: contar los ancestros con un valor más pequeño para cada Node de un árbol binario . La idea es usar DFS para cada Node y se puede extender fácilmente a un árbol N-ario .

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque eficiente se basa en el concepto de Ordered_set , estructura de datos basada en políticas y DFS .

• Use un DFS de arriba hacia abajo para atravesar desde la raíz a todos los Nodes y use un conjunto ordenado para almacenar valores de todos los Nodes en la ruta desde la raíz hasta el Node actual.
• Cada vez que ingrese a un Node, antes de llamar a DFS en sus hijos, inserte el índice del Node en el conjunto ordenado y cada vez que salgamos del Node, borre el índice del Node del conjunto_ordenado. Esto asegura que order_set contendrá valores de todos los ancestros del Node actual.
• Dado que el conjunto ordenado brinda la funcionalidad de devolver una cantidad de valores más pequeños que x dados al encontrar el orden de x , para cada Node, siempre que ingrese al Node, simplemente encuentre el orden del índice del Node actual y obtenga la cantidad de valores más pequeños presentes en el conjunto_ordenado, es decir, el número de ancestros de menor valor para cada Node.
• Use un mapa para almacenar la cantidad de ancestros de menor valor para cada Node y utilícelo para imprimir la respuesta final.

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

// C++ program for the above approach
#include <bits/stdc++.h>
  
// Common file
#include <ext/pb_ds/assoc_container.hpp>
  
// Including tree_order_statistics_node_update
#include <ext/pb_ds/tree_policy.hpp>
  
using namespace std;
using namespace __gnu_pbds;
  
// Declaring ordered_set
typedef tree<int, null_type, less<int>,
             rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
  
// Map to store final ans for each node
unordered_map<int, int> ans;
  
// Function to add an edge
// between nodes u and v
void addEdge(vector<int> adj[],
             int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
  
// Function to count the number of
// ancestors with values smaller
// than that of the current node
void countSmallerAncestors(
    vector<int> adj[],
    int root, int par,
    ordered_set& ancestors)
{
  
    // Map current node to
    // number of smaller valued ancestors
    ans[root] = ancestors.order_of_key(root);
  
    // Add current node to path
    ancestors.insert(root);
    for (int node : adj[root]) {
  
        // Avoid cycles
        if (node != par) {
            countSmallerAncestors(
                adj, node,
                root, ancestors);
        }
    }
  
    // Remove current node from path
    ancestors.erase(root);
}
  
// Driver Code
int main()
{
    // Number of nodes in graph
    int N = 7;
  
    // Initialize graph
    vector<int> adj[N + 1];
  
    // Tree Formation
    addEdge(adj, 1, 5);
    addEdge(adj, 1, 4);
    addEdge(adj, 4, 6);
    addEdge(adj, 5, 3);
    addEdge(adj, 5, 2);
    addEdge(adj, 5, 7);
  
    // Ordered set to store values in path
    // from root to current node in dfs
    ordered_set ancestors;
  
    countSmallerAncestors(adj, 1, -1, ancestors);
  
    for (int i = 1; i <= N; i++) {
        cout << ans[i] << " ";
    }
  
    return 0;
}

0 1 1 1 1 2 2

Complejidad temporal: O(N * log(N)).
Espacio Auxiliar:  O(N).