Recuento de Nodes a la distancia K de S en su subárbol para consultas Q

Dado un árbol que consiste en N Nodes y arraigado en el Node 1 , también dado un arreglo Q[] de M pares , donde cada elemento del arreglo representa una consulta de la forma (S, K) . La tarea es imprimir el número de Nodes a la distancia K en el subárbol del Node S para cada consulta (S, K) del arreglo.

Ejemplos: 

Entrada:  Q[] = {{2, 1}, {1, 1}},  

Salida: 3 
             2
Explicación: 

1. Consulta (2, 1): Imprimir 3, ya que hay 3 Nodes 4, 5 y 6 a la distancia de 1 en el subárbol del Node 2.
2. Consulta (1, 1): Imprimir 2, ya que hay 2 Nodes 2 y 3 a la distancia de 1 en el subárbol del Node 1.

Entrada: Bordes = {{1, 2}, {2, 3}, {3, 4}}, Q[] = {{1, 2}, {2, 2}}
Salida: 1 1

Enfoque ingenuo: el enfoque más simple es que cada consulta ejecute una búsqueda en profundidad (DFS) desde el Node S y encuentre todos los Nodes que están a una distancia K de un Node S determinado . 

Complejidad temporal: O(N*Q)
Espacio auxiliar: O(1)

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

1. Supongamos que tin[] almacena el tiempo de entrada de cada Node y tout[] almacena el tiempo de salida de un Node de acuerdo con el recorrido dfs del árbol.
2. Entonces, para dos Nodes, A y B , B estará en el subárbol de A si y solo si:
   • tin[B]≥tin[A] y tout[B]≤tout[A]
3. Supongamos que level[] , donde level[i] almacena los tiempos de entrada de todos los Nodes presentes en la profundidad i .
4. Entonces, usando búsqueda binaria , se pueden encontrar Nodes a una distancia K de un Node.

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

• Inicialice tres arrays , digamos tin[] , tout[] y depth[] para almacenar el tiempo de entrada, el tiempo de salida y la profundidad de un Node, respectivamente.
• Inicialice dos vectores 2D , digamos adj ylevels , para almacenar la lista de adyacencia y los tiempos de entrada de cada Node a una profundidad específica.
• Inicialice una variable, digamos t como 1, para realizar un seguimiento del tiempo.
• Defina una función DFS recursiva , diga dfs(node, parent, d) y realice los siguientes pasos:
  • Asigne t a tin[node] y luego incremente t en 1.
  • Empuje tin[node] en los niveles de vector [d] y luego asigne d a depth[node].
  • Iterar sobre los hijos del Node y llamar a la función recursiva como dfs(X, Node, d+1) para cada hijo X.
  • Después de los pasos anteriores, asigne t a tout[Node] e incremente t en 1.
• Llame a la función recursiva dfs(1, 1, 0).
• Recorra la array Q[] usando la variable i y haga lo siguiente:
  • Almacene el valor del elemento de array actual como S = Q[i].primero y K = Q[i].segundo.
  • Encuentre el recuento de todos los Nodes mayores que tin[S] en los niveles vectoriales [profundidad[S]+K] y guárdelo en una variable, digamos L.
  • Encuentre el recuento de todos los Nodes mayores que tout[S] en los niveles de vector [profundidad[S]+K] y guárdelo en una variable, digamos R.
  • Imprime el valor de RL como respuesta a la consulta actual.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int tin[100], tout[100], depth[100];
int t = 0;
 
// Function to add edges
void Add_edge(int parent, int child,
              vector<vector<int> >& adj)
{
    adj[parent].push_back(child);
    adj[child].push_back(parent);
}
 
// Function to perform Depth First Search
void dfs(int node, int parent, vector<vector<int> >& adj,
         vector<vector<int> >& levels, int d)
{
    // Stores the entry time of a node
    tin[node] = t++;
 
    // Stores the entering time
    // of a node at depth d
    levels[d].push_back(tin[node]);
    depth[node] = d;
 
    // Iterate over the children of node
    for (auto x : adj[node]) {
        if (x != parent)
            dfs(x, node, adj, levels, d + 1);
    }
 
    // Stores the Exit time of a node
    tout[node] = t++;
}
 
// Function to find number of nodes
// at distance K from node S in the
// subtree of S
void numberOfNodes(int node, int dist,
                   vector<vector<int> >& levels)
{
    // Distance from root node
    dist += depth[node];
 
    // Index of node with greater tin value
    // then tin[S]
    int start = lower_bound(levels[dist].begin(),
                            levels[dist].end(), tin[node])
                - levels[dist].begin();
 
    // Index of node with greater tout value then tout[S]
    int ed = lower_bound(levels[dist].begin(),
                         levels[dist].end(), tout[node])
             - levels[dist].begin();
 
    // Answer to the Query
    cout << ed - start << endl;
}
 
// Function for performing DFS
// and answer to queries
void numberOfNodesUtil(pair<int, int> Q[], int M, int N)
{
 
    vector<vector<int> > adj(N + 5), levels(N + 5);
 
    Add_edge(1, 2, adj);
    Add_edge(1, 3, adj);
    Add_edge(2, 4, adj);
    Add_edge(2, 5, adj);
    Add_edge(2, 6, adj);
 
    t = 1;
 
    // DFS function call
    dfs(1, 1, adj, levels, 0);
 
    // Traverse the array Q[]
    for (int i = 0; i < M; ++i) {
        numberOfNodes(Q[i].first, Q[i].second, levels);
    }
}
 
// Driver Code
int main()
{
    // Input
    int N = 6;
    pair<int, int> Q[] = { { 2, 1 }, { 1, 1 } };
    int M = sizeof(Q) / sizeof(Q[0]);
 
    // Function call
    numberOfNodesUtil(Q, M, N);
}

# Python3 program for the above approach
from bisect import bisect_left, bisect_right
 
tin = [0] * 100
tout = [0] * 100
depth = [0] * 100
t = 0
 
# Function to add edges
def Add_edge(parent, child, adj):
     
    adj[parent].append(child)
    adj[child].append(parent)
    return adj
 
# Function to perform Depth First Search
def dfs(node, parent, d):
     
    global tin, tout, depth, adj, levels, t
     
    # Stores the entry time of a node
    tin[node] = t
    t += 1
 
    # Stores the entering time
    # of a node at depth d
    levels[d].append(tin[node])
    depth[node] = d
 
    # Iterate over the children of node
    for x in adj[node]:
        if (x != parent):
            dfs(x, node, d + 1)
 
    # Stores the Exit time of a node
    tout[node] = t
    t += 1
 
# Function to find number of nodes
# at distance K from node S in the
# subtree of S
def numberOfNodes(node, dist):
     
    global levels, tin, tout
     
    # Distance from root node
    dist += depth[node]
 
    # Index of node with greater tin value
    # then tin[S]
    start = bisect_left(levels[dist], tin[node])
 
    # Index of node with greater tout value then tout[S]
    ed = bisect_left(levels[dist], tout[node])
 
    # Answer to the Query
    print(ed - start)
 
# Function for performing DFS
# and answer to queries
def numberOfNodesUtil(Q, M, N):
     
    global t, adj
 
    adj = Add_edge(1, 2, adj)
    adj = Add_edge(1, 3, adj)
    adj = Add_edge(2, 4, adj)
    adj = Add_edge(2, 5, adj)
    adj = Add_edge(2, 6, adj)
 
    t = 1
 
    # DFS function call
    dfs(1, 1, 0)
 
    # Traverse the array Q[]
    for i in range(M):
        numberOfNodes(Q[i][0], Q[i][1])
 
# Driver Code
if __name__ == '__main__':
     
    # Input
    N = 6
    Q = [ [ 2, 1 ], [ 1, 1 ] ]
 
    M = len(Q)
 
    adj = [[] for i in range(N+5)]
    levels = [[] for i in range(N + 5)]
 
    # Function call
    numberOfNodesUtil(Q, M, N)
 
# This code is contributed by mohit kumar 29

3
2

Complejidad de tiempo: O(N + M*log(N))
Espacio auxiliar: O(N)