树中不同路径的数量，该路径中的节点值大于或等于 K

Question

问题陈述：
给你一个整数 N 表示该树中的节点数。现在，您需要计算树中有多少条不同的路径，使得该路径中的最小节点值大于或等于 k.

输入格式：

第一行包含该树中的节点总数 N 和一个正整数值 K.
下 N-1 行包含一对整数 u, v （值不是逗号分隔），表示节点 u 和 v 之间有一条边, 在树上。

示例：

输入：

预期输出：

编辑：我想不出如何解决这个问题。所以，请给我一个提示，以便我可以进一步尝试实现它。即使是最微小的帮助，我也会很感激。

更新：

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

这种问题的幼稚做法在任何情况下都不会通过。解决方案的复杂性应该是 O(n**2) 或 O(nlogn)。

Answer 1

让我们以更简单的情况来解决这个问题，假设树中的所有节点都大于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

Answer 2

这个问题可以用树上的动态规划来解决，你可以在这里阅读https://www.geeksforgeeks.org/dynamic-programming-trees-set-2/。

让我们把问题分成两部分，第一部分是找到节点子树中有效路径的数量u。第二部分是找到节点 u 的答案，如果我们不考虑它的子树而是去它的 parent 等等。

让我们将 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[]，如果我们不考虑 u 的子树，则 out[u] 是有效的路径数u 的 parent 等等。

让我们调用 u P[u] 的 parent。要计算 out[u]，我们将依赖 p[u]。 out[i] 是如果我们去 p[u] 的有效路径数，一旦我们到达 p[u] 我们可以做的是遍历它的子树（不包括 u 的分支当然）或访问 p[p[u]]（u 的 parent 的 parent）所以 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 3

对于树，假设我们枚举的路径是从上到下的方向，我们可以递归地制定它。让 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

从树根调用 f 后，答案将是 a + b。

输出：

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

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

树中不同路径的数量，该路径中的节点值大于或等于 K

Number of distinct paths in tree, that have value of nodes in that path greater than or equal K

algorithm

tree

graph-theory

n-ary-tree

python-3.x