Количество различных путей в дереве, у которых значение узлов в этом пути больше или равно K

Question

Постановка задачи:
Вам дано целое число N, обозначающее количество узлов в этом дереве.Теперь вам нужно посчитать, сколько разных путей есть в дереве, так что минимальное значение узла в этом пути больше или равно k.

Формат ввода:

1. Первая строка содержит общее количество узлов N в этом дереве и положительное целочисленное значение K.
2. Следующие N-1 строки содержат пару целых чисел u, v (значения не являются запятымиразделено), что означает наличие ребра между узлами u и v в дереве.

Пример:

Ввод:

4 2  
1 2  
2 3  
3 4  

Ожидаемый результат:

3

Редактировать: Я не могу придумать, как подойти к этой проблеме.Поэтому, пожалуйста, предоставьте мне подсказку, чтобы я мог попробовать ее реализовать.Я буду благодарен даже малейшей помощи.

Обновление:

1 <= N <= 10^5
1 <= u,v <= N  
1 <= K <= 10^6  

Наивный подход к такой проблеме не пройдет ни при каких обстоятельствах.Сложность решения должна быть либо O (n ** 2), либо O (nlogn).

Answer 1

Эту проблему можно решить с помощью динамического программирования на деревьях, о ней вы можете прочитать здесь https://www.geeksforgeeks.org/dynamic-programming-trees-set-2/.

Давайте разделим задачу на две части, первая - найти количество допустимых путейв поддереве узла u.Вторая часть состоит в том, чтобы найти ответ для узла u, если мы не рассматриваем его поддерево, а обращаемся к его родителю и т. Д.

Давайте рассмотрим 1 как корень дерева.

Теперь для решения первой части мы создадим массив in[], в котором мы будем хранить количество путей в поддереве узла u, поэтому in[u] будет представлять количество допустимых путей, начиная сузел u и посещение его поддерева.Чтобы вычислить этот массив, мы можем запустить простой dfs следующим образом:

//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)
            }
        }
    }
}

Для решения второй части нам нужен массив out[], где out[u] - это число путей, которые действительны, если мы нерассмотрим поддерево u, которое идет к родителю u и так далее.

Давайте позвоним родителю u P[u].Для вычисления out[u] мы будем полагаться на p[u].out[i] - это число допустимых путей, если мы перейдем к p[u], и что мы можем сделать, когда достигнем p[u], это либо пройти через его поддерево (исключая, конечно, u) или посетить p[p[u]] (родительский элемент для u), поэтому out[u] равен (out[p[u]] + 1) + (in[p[u]] - in[u] - 1).

// 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
        }
    }
}

Чтобы найти ответ, просто сложите все out[u] + in[u] для всех узлов и разделите на 2, потому что каждый путь был вычислендважды.

сложность O (V + E)

Answer 2

Для деревьев, предполагая, что пути, которые мы перечисляем, направлены сверху вниз, мы можем сформулировать это рекурсивно.Пусть f(T, k) представляет кортеж, [a, b], где a - количество различных допустимых путей в T, которые начинаются с T;и b - количество различных допустимых путей в T, которые начинаются с нижнего узла.Все узлы в допустимых путях имеют значение, большее или равное k.

Тогда (код Python):

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

Ответ будет тогда a + b после вызова f от корня дерева.

Вывод:

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

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

Answer 3

Давайте решим эту проблему в более простом случае, предположим, что все узлы в дереве больше k, поэтому число допустимых путей равно nC2.

И мы также делаемОбратите внимание, что действительный путь не может содержать ни одного узла, который меньше k, поэтому нам нужно удалить все узлы, которые меньше k, из дерева, что создаст поддерево n - k, таким образом, конечный результатбудет

result = sum of nC2 of all subtree

Простой алгоритм:

remove all edges that connect to nodes that less than k

for each node that >= k and not marked as visited
  do bfs to count number of node in that subtree
  result += nC2

return result