Número de caminos de longitud K en un árbol

Dado un árbol de N Nodes y un número entero K , la tarea es encontrar el número total de caminos que tienen una longitud K.

Ejemplos:

Entrada: N = 5, K = 2
árbol = 1
                   / \
                 2 5
               / \
             3 4
Salida: 4
Explicación: Los caminos que tienen longitud 2 son
1 – 2 – 3, 1 – 2 – 4, 2 – 1 – 5, 3 – 2 – 4

Entrada: N = 2, K = 2
árbol = 1
                /
              2
Salida: 0
Explicación: No hay camino en el árbol que tenga longitud 2.

Intuición: la idea principal es encontrar las rutas de longitud K de cada Node y agregarlas.

1. Encuentre el número de caminos de longitud K ‘originados’ desde un Node ‘Node’ dado. ‘Original’ aquí significa que ‘Node’ tendrá la menor profundidad entre todos los Nodes en la ruta. Por ejemplo, las rutas de 2 longitudes que se originan en 1 se muestran en el siguiente diagrama.
2. Sume el valor anterior para todos los Nodes y será la respuesta requerida.

Enfoque ingenuo: para calcular las rutas de longitud K que se originan en el ‘Node’, se utilizan dos DFS . Digamos que todo este proceso es: paths_originating_from(node)

1. Supongamos que el ‘Node’ tiene varios hijos y actualmente se está procesando el hijo ‘u’.
2. Para todos los hijos anteriores se ha calculado la frecuencia de Nodes a una determinada profundidad. Más formalmente, freq[d] proporciona el número de Nodes en la profundidad ‘d’ cuando solo se han procesado los elementos secundarios de ‘Node’ antes de ‘u’.
3. Si hay un Node ‘x’ en la profundidad ‘d’, el número de caminos de longitud K que se originan en el ‘Node’ y pasan por ‘x’ será freq[K – d].
4. El primer DFSF contribuiría a la respuesta final y el segundo DFS actualizaría la array freq[] para uso futuro.
5. Sume ‘paths_originating_from(node)’ para todos los Nodes del árbol, esta será la respuesta requerida.

Vea la imagen a continuación para comprender mejor el segundo punto.

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

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
  
int mx_depth = 0, ans = 0;
int N, K;
vector<int> freq;
vector<vector<int> > g;
  
// This dfs is responsible for calculating ans 
// and updating freq vector
void dfs(int node, int par, int depth, 
         bool contri)
{
    if (depth > K)
        return;
    mx_depth = max(mx_depth, depth);
  
    if (contri) {
        ans += freq[K - depth];
    }
    else {
        freq[depth]++;
    }
  
    for (auto nebr : g[node]) {
        if (nebr != par) {
            dfs(nebr, node, depth + 1, 
                contri);
        }
    }
}
  
// Function to calculate K length paths 
// originating from node
void paths_originating_from(int node, 
                            int par)
{
    mx_depth = 0;
    freq[0] = 1;
  
    // For every not-removed nebr, 
    // calculate its contribution, 
    // then update freq vector for it
    for (auto nebr : g[node]) {
        if (nebr != par) {
            dfs(nebr, node, 1, true);
            dfs(nebr, node, 1, false);
        }
    }
  
    // Re-initialize freq vector
    for (int i = 0; i <= mx_depth; ++i) {
        freq[i] = 0;
    }
  
    // Repeat the same for children
    for (auto nebr : g[node]) {
        if (nebr != par) {
            paths_originating_from(nebr, 
                                   node);
        }
    }
}
  
// Utility method to add edges to tree
void edge(int a, int b)
{
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
}
  
// Driver code
int main()
{
    N = 5, K = 2;
    freq = vector<int>(N);
    g = vector<vector<int> >(N);
  
    edge(1, 2);
    edge(1, 5);
    edge(2, 3);
    edge(2, 4);
    
    paths_originating_from(0, -1);
    cout << ans << endl;
}

4

Complejidad de tiempo: O(N * H) donde H es la altura del árbol que puede ser N al máximo
Espacio auxiliar: O(N)

Enfoque eficiente: este enfoque se basa en el concepto de descomposición centroide . Los pasos son los siguientes:

1. Encuentre el centroide del árbol actual T .
2. Todos los Nodes ‘no eliminados’ accesibles desde T pertenecen a su subárbol. Llame a paths_originating_from(T) , luego marque T como ‘eliminado’.
3. Repita el proceso anterior para todos los vecinos ‘no eliminados’ de T .

La siguiente figura muestra un árbol con el centroide actual y su subárbol. Tenga en cuenta que los Nodes con bordes gruesos ya se han seleccionado como centroides anteriormente y no pertenecen al subárbol del centroide actual.

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

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
  
// Struct for centroid decomposition
struct CD {
    // 1. mx_depth will be used to store 
    // the height of a node
    // 2. g[] is adjacency list for tree
    // 3. freq[] stores frequency of nodes 
    // at particular height, it is maintained 
    // for children of a node
    int n, k, mx_depth, ans;
    vector<bool> removed;
    vector<int> size, freq;
    vector<vector<int> > g;
  
    // Constructor for struct
    CD(int n1, int k1)
    {
        n = n1;
        k = k1;
        ans = mx_depth = 0;
  
        g.resize(n);
        size.resize(n);
        freq.resize(n);
        removed.assign(n, false);
    }
  
    // Utility method to add edges to tree
    void edge(int u, int v)
    {
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
  
    // Finds size of a subtree, 
    // ignoring removed nodes in the way
    int get_size(int node, int par)
    {
        if (removed[node])
            return 0;
        size[node] = 1;
  
        for (auto nebr : g[node]) {
            if (nebr != par) {
                size[node] += get_size(nebr, 
                                       node);
            }
        }
  
        return size[node];
    }
  
    // Calculates centroid of a subtree 
    // of 'node' of size 'sz'
    int get_centroid(int node, int par, 
                     int sz)
    {
        for (auto nebr : g[node]) {
            if (nebr != par && !removed[nebr]
                && size[nebr] > sz / 2) {
                return get_centroid(nebr, 
                                    node, sz);
            }
        }
        return node;
    }
  
    // Decompose the tree 
    // into various centroids
    void decompose(int node, int par)
    {
        get_size(node, -1);
  
        // c is centroid of subtree 'node'
        int c = get_centroid(node, par, 
                             size[node]);
  
        // Find paths_originating_from 'c'
        paths_originating_from(c);
  
        // Mark this centroid as removed
        removed = true;
  
        // Find other centroids
        for (auto nebr : g) {
            if (!removed[nebr]) {
                decompose(nebr, c);
            }
        }
    }
  
    // This dfs is responsible for 
    // calculating ans and 
    // updating freq vector
    void dfs(int node, int par, int depth,
             bool contri)
    {
        if (depth > k)
            return;
        mx_depth = max(mx_depth, depth);
  
        if (contri) {
            ans += freq[k - depth];
        }
        else {
            freq[depth]++;
        }
  
        for (auto nebr : g[node]) {
            if (nebr != par && 
                !removed[nebr]) {
                dfs(nebr, node, 
                    depth + 1, contri);
            }
        }
    }
  
    // Function to find K-length paths
    // originating from node
    void paths_originating_from(int node)
    {
        mx_depth = 0;
        freq[0] = 1;
  
        // For every not-removed nebr, 
        // calculate its contribution, 
        // then update freq vector for it
        for (auto nebr : g[node]) {
            if (!removed[nebr]) {
                dfs(nebr, node, 1, true);
                dfs(nebr, node, 1, false);
            }
        }
          
        // Re-initialize freq vector
        for (int i = 0; i <= mx_depth; ++i) {
            freq[i] = 0;
        }
    }
};
  
// Driver code
int main()
{
    int N = 5, K = 2;
  
    CD cd_s(N, K);
    cd_s.edge(1, 2);
    cd_s.edge(1, 5);
    cd_s.edge(2, 3);
    cd_s.edge(2, 4);
  
    cd_s.decompose(0, -1);
    cout << cd_s.ans;
    return 0;
}

4

Complejidad de tiempo: O(N * log(N)) donde log N es la altura del árbol
Espacio auxiliar: O(N)