树中不同路径的数量，该路径中的节点值大于或等于 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[]，如果我们不考虑u的子树，则out[u]是有效的路径数，该子树将转到u的父级，依此类推。

让我们打电话给uP[u]的父母。要计算out[u]我们将依靠p[u]. 如果我们去p[u]，out[i]是有效路径的数量，一旦我们到达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

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

对于树，假设我们枚举的路径是从上到下定向的，我们可以递归地表述它。设f(T, k)表示一个元组，[a, b]，其中a是T中从T开始的不同有效路径的数量;和b，T中从较低节点开始的不同有效路径的数量。有效路径中的所有节点的值都大于或等于k。

然后(蟒蛇代码)：

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]