from typing import Iterable
from typing import Tuple


def get_maximum_path(tree_level_strings: Iterable[str]) -> Tuple[int, Iterable[int]]:
    """Get maximum path value and maximum path for a given tree, represented as level strings.

    Solution idea: Compute maximum path from *bottom up*. Hence, the time complexity is linear.
    """
    tree_levels = [
        [int(number_string) for number_string in tree_level_string.split()] \
            for tree_level_string in tree_level_strings
    ]

    max_path_tree_levels = [[(value, -1) for value in tree_levels[-1]]]
    for level_idx in range(len(tree_levels) - 2, -1, -1):
        current_tree_level = tree_levels[level_idx]
        previous_path_tree_level = max_path_tree_levels[-1]
        new_path_tree_level = []
        for idx, value in enumerate(current_tree_level):
            left_val = previous_path_tree_level[idx][0]
            right_val = previous_path_tree_level[idx + 1][0]
            if left_val >= right_val:
                new_path_tree_node = (value + left_val, 0)
            else:
                new_path_tree_node = (value + right_val, 1)
            new_path_tree_level.append(new_path_tree_node)
        max_path_tree_levels.append(new_path_tree_level)

    max_path_tree_levels.reverse()

    max_path_tree = []
    node_idx = 0
    for level_idx, level in enumerate(max_path_tree_levels):
        max_path_tree.append(tree_levels[level_idx][node_idx])
        node_idx += level[node_idx][1]

    return max_path_tree_levels[0][0][0], max_path_tree