Nombre de chemins distincts dans l'arborescence, qui ont une valeur de nœuds dans ce chemin supérieure ou égale à K

Ce problème peut être résolu en utilisant la programmation dynamique sur les arbres, vous pouvez en savoir plus ici https://www.geeksforgeeks.org/dynamic-programming-trees-set-2/ .

Séparons le problème en deux parties, la première est de trouver le nombre de chemins qui sont valides dans le sous-arbre d'un nœud u . La deuxième partie est de trouver la réponse pour le nœud u si nous ne considérons pas son sous-arbre mais en allant à son parent et ainsi de suite.

Considérons 1 comme la racine de l'arborescence.

Maintenant pour résoudre la première partie, nous allons créer un tableau dans [] dans lequel nous allons stocker le le nombre de chemins dans le sous-arbre du nœud u donc dans [u] représentera le nombre de chemins valides à partir du nœud u et en visitant son sous-arbre. Pour calculer ce tableau, nous pouvons exécuter un simple dfs comme suit:

// u is the current node - p is the parent
void dfs2(int u, int p) {
    for (int i = 0; i < g[u].size(); i++) { // iterate through the adjacency of node u
        int v = g[u][i]; // v is the child of u
        if (v != p) { // in case v is the parent just ignore it
            if (v >= k && u >= k) { // if value of u or v is less than k then we cant start at this node so it should be 0
                out[v] += (out[u] + 1); //add to the number of paths of v the number of paths from it's parent (u) + 1 if we dont use the subtree of u
                out[v] += (in[u] - in[v] - 1); // add to the number of paths of v the number of paths from it's parent (u)
                // we should subtract in[v] + 1 because we want to exclude this branch from the subtree of the parent
            }
            dfs2(v, u); // go to node v
        }
    }
}

Pour résoudre la deuxième partie, nous avons besoin d'un tableau out [] avec out [u] étant le nombre de chemins valides si l'on ne considère pas le sous-arbre de u qui va au parent de u et ainsi sur.

permet d'appeler le parent de u P [u] . Pour calculer out [u] nous nous baserons sur p [u] . out [i] est le nombre de chemins valides si nous allons à p [u] , et ce que nous pouvons faire une fois que nous atteignons p [u] code > est soit passer par son sous-arbre (à l'exclusion de la brach de u bien sûr) ou visiter p [p [u]] (le parent du parent de u ) donc out [u] est (out [p [u]] + 1) + (in [p [u]] - in [u] - 1) code>.

//u is the current node - p is the parent
void dfs1(int u, int p) {
    for (int i = 0; i < g[u].size(); i++) { //iterate through the adjacency of node u
        int v = g[u][i]; // v is the child of u
        if (v != p) { //in case v is the parent just ignore it
            dfs1(v, u); //go to node v
            if (u >= k && v >= k) { //if value of u or v is less than k then we cant start at this node so it should be 0
                in[u] += in[v] + 1; //add to number of paths of u the number of paths starting from the node v + 1 (+1 because we can also go from u to v)
            }
        }
    }
}

Pour trouver la réponse, additionnez simplement tout out [u] + in [u] pour tous les nœuds et divisez par 2 car chaque chemin a été calculé deux fois.

complexité O (V + E)

Pour les arbres, en supposant que les chemins que nous énumérons sont dirigés de haut en bas, nous pouvons le formuler récursivement. Soit f (T, k) un tuple, [a, b] , où a est le nombre de chemins valides distincts dans T qui commencent à T ; et b , le nombre de chemins valides distincts dans T qui commencent à un nœud inférieur. Tous les nœuds dans des chemins valides ont une valeur supérieure ou égale à k .

Alors (code Python):

T = {
  "value": 1,
  "children": [
    {
      "value": 2,
      "children": [
        {
          "value": 3,
          "children": [
            {
              "value": 4,
              "children": []
            }
          ]
        }
      ]
    }
  ]
}

print f(T, 2)  # [0, 3]

La réponse serait alors be a + b , après avoir appelé f depuis la racine de l'arborescence.

Sortie:

def f(T, k):
  if not T["children"]:
    return [0, 0]

  result = [0, 0]

  for c in T["children"]:
    [a, b] = f(c, k)
    result[1] += a + b

    if T["value"] >= k <= c["value"]:
      # One valid path from T to c
      # plus extending all the paths
      # that start at c
      result[0] += 1 + a

  return result

p>