Maximum Sum Path in a Binary Tree

Given a binary tree, where each node contains an integer value, your task is to find the maximum sum obtainable by traversing from the root to any leaf node. Each node in the tree is represented by a tuple of four integers: (node_id, value, left_child, right_child), where the left_child and right_child are indices of the left and right child nodes, respectively, and -1 indicates the absence of a child.

The problem can be mathematically described by the recurrence:

where $v_i$ is the value at node $i$, and $l_i$, $r_i$ denote its left and right child nodes.

Implement functions to build the binary tree from the input, and then compute and output the maximum sum from the root to any leaf. The input is provided via standard input (stdin) and output should be written to standard output (stdout).

inputFormat

The first line contains an integer $n$, the number of nodes in the binary tree. Each of the following $n$ lines includes four integers: node_id, value, left_child, and right_child, where left_child and right_child are the indices of the left and right children, respectively (with -1 indicating a missing child).

outputFormat

Output a single integer representing the maximum sum from the root node to any leaf node.## sample

5
0 5 1 2
1 3 3 -1
2 2 -1 4
3 7 -1 -1
4 8 -1 -1

20