Problem 2.3: General Rooted Path (100pts)

Problem

A general rooted path of a tree differs from a rooted path in that it can start from any node, going down the tree. Formally, a general rooted path is a list of adjacent nodes \(v\_1, v\_2, \dots, v\_n\) where for each \(i\), \(v\_{i + 1}\) is a child of \(v\_i\).

In this problem, given a tree t where all node values are integers, you need to count how many general rooted paths in t have a sum of at least n. You can use the function bigpath you implemented in Problem 2.2 to help your implementation.

树的一般有根路径（general rooted path）与（标准的）有根路径不同之处在于，它可以从树中的任何节点开始，并沿着树向下延伸。形式上，一个一般有根路径是相邻节点的列表 \(v_1, v_2, \dots, v_n\)，其中对于每个 \(i\)，\(v_{i+1}\) 是 \(v_i\) 的子节点。

在这个问题中，给定一棵树 t，其中所有节点值都是整数，您需要计算 t 中路径总和至少为 \(n\) 的一般有根路径有多少条。 您可以使用您在问题 2.2 中实现的函数 bigpath 来帮助您的实现。

def bigger_path(t, n):
    """Return the number of general rooted paths in t that have a sum larger or equal to n.

    >>> t = tree(1, [tree(2), tree(3, [tree(4), tree(5)])])
    >>> bigger_path(t, 3)
    9
    >>> bigger_path(t, 6)
    4
    >>> bigger_path(t, 9)
    1
    """
    "*** YOUR CODE HERE ***"

Hints

Solutions

Generated by AI.

Generated by AI.

---

one-liner

def bigger_path(t, n):
    return bigpath(t, n) + sum([bigger_path(i, n) for i in branches(t)])