# Problem Solving

from __future__ import annotations
from dataclasses import dataclass, field

@dataclass
class Tree[T]:
    """A Tree has a label (of type T) and a list of branches, which are trees.

    >>> t = Tree(2, [Tree(1), Tree(1, [Tree(0), Tree(1)])])
    >>> isinstance(t, Tree)
    True
    >>> t.label
    2
    >>> t.branches[1].label
    1
    >>> print(t)
    2
      1
      1
        0
        1
    """
    label: T
    branches: list[Tree[T]] = field(default_factory=list)  # branches defaults to []

    def __str__(self):
        return format_tree(self)

def format_tree(t: Tree, indent='') -> str:
    "Format a tree with each branch indented below its label."
    assert isinstance(t, Tree), f'{t!r} is not a Tree'
    assert isinstance(t.branches, list), f'branches of {t!r} is not a list'
    string = indent + str(t.label)
    for b in t.branches:
        string += '\n' + format_tree(b, indent + '  ')
    return string

def is_leaf(t: Tree) -> bool:
    return not t.branches

# Solving Tree Problems

def bigs(t: Tree[int]):
    """Return the number of nodes in t that are larger than all their ancestors.

    >>> a = Tree(1, [Tree(4, [Tree(4), Tree(5)]), Tree(3, [Tree(0, [Tree(2)])])])
    >>> bigs(a)
    4
    """
    def f(a, x):
        if a.label > x:
            return 1 + sum([f(b, a.label) for b in a.branches])
        else:
            return sum([f(b, x) for b in a.branches])
    return f(t, t.label - 1)

# Applying the Design Process

def one(b):
    if b:
        return 1
    else:
        return 0

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

    >>> t = Tree(1, [Tree(2), Tree(3, [Tree(4), Tree(5)])])
    >>> count_big(t, 3)
    3
    >>> count_big(t, 6)
    2
    >>> count_big(t, 9)
    1
    """
    if is_leaf(t):
        return one(t.label >= n)
    else:
        return sum([count_big(b, n - t.label) for b in t.branches])

def print_big(t, n):
    """Print the paths in t that have a sum larger or equal to n.

    >>> t = Tree(1, [Tree(2), Tree(3, [Tree(4), Tree(5)])])
    >>> print_big(t, 3)
    [1, 2]
    [1, 3, 4]
    [1, 3, 5]
    >>> print_big(t, 6)
    [1, 3, 4]
    [1, 3, 5]
    >>> print_big(t, 9)
    [1, 3, 5]
    """
    def helper(t, p):
        p = p + [t.label]
        if is_leaf(t):
            if sum(p) >= n:
                print(p)
        else:
            for b in t.branches:
                helper(b, p)
    helper(t, [])

def only_paths(t: Tree[int], n: int) -> Tree[int] | None:
    """Return a Tree with only the nodes of t that are on a path from the root
    to a leaf with labels that sum to n, or None if no path sums to n.

    >>> t = Tree(3, [Tree(4), Tree(1, [Tree(3, [Tree(2)]), Tree(2, [Tree(1)]), Tree(5), Tree(3)])])
    >>> print(only_paths(t, 7))
    3
      4
      1
        2
          1
        3
    >>> u = Tree(3, [Tree(4), Tree(5, [Tree(6)]), Tree(7), Tree(8, [Tree(9), Tree(10)])])
    >>> print(only_paths(u, 2))
    None
    """
    if is_leaf(t) and t.label == n:
        return t
    new_branches = [only_paths(b, n - t.label) for b in t.branches]
    if any(new_branches):
        return Tree(t.label, [b for b in new_branches if b != None])