Problem 2.2: Rooted Path (100pts)

Problem

Define a rooted path of a tree to be a path that starts from the root going down to any node in the tree. Formally, a rooted path is a list of adjacent nodes \(v\_1, v\_2, \dots, v\_n\) where \(v\_1\) is the root of the tree, and for each \(i\), \(v\_{i + 1}\) is a child of \(v\_i\).

For example, in the tree tree(1, [tree(2), tree(3, [tree(4), tree(5)])]), the following lists are all rooted paths:
[1]
[1, 2]
[1, 3]
[1, 3, 4]
[1, 3, 5]
In this problem, given a tree t where all node values are integers, you need to first find all rooted paths in t, then count how many of them have a sum of at least n. Here, the sum of a path is defined to be the sum of all node values in that path.

Implement bigpath, which takes a tree t and an integer n. It returns the number of paths in t whose sum is at least n.

定义树的有根路径（rooted path）为一条从根节点开始向下延伸到树中任意节点的路径。形式上，一个有根路径是相邻节点的列表 \(v_1, v_2, \dots, v_n\)，其中 \(v_1\) 是树的根节点，并且对于每个 \(i\)， \(v_{i+1}\) 是 \(v_i\) 的子节点。

例如，在树 tree(1, [tree(2), tree(3, [tree(4), tree(5)])]) 中，以下列表都是有根路径：

[1]
[1, 2]
[1, 3]
[1, 3, 4]
[1, 3, 5]

在这个问题中，给定一棵树 t，其中所有节点值都是整数，您需要首先找到 t 中所有的有根路径，然后计算其中有多少条路径的总和至少为 \(n\)。这里，路径的总和定义为该路径中所有节点值的总和。

实现函数 bigpath，它接受一个树 t 和一个整数 \(n\)。它返回树 t 中路径总和至少为 \(n\) 的路径数量。

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

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

Hints

Solutions

Generated by AI.

one-liner:

def bigpath(t, n):
    return (1 if label(t) >= n else 0) + sum([bigpath(i, n - label(t)) for i in branches(t)])