Maximum Depth Path Sum
Given a rooted tree where each node has a value, find the maximum sum of values along any root-to-leaf path. The tree is represented by a parent array, where parent[i] is the parent of node i, and parent[0] is -1, indicating that node 0 is the root. Node values are given in a separate array.
Input
The first line contains an integer N (1 <= N <= 200000), the number of nodes. The second line contains N integers, parent, where parent[i] is the parent of node i. parent[0] is -1. The third line contains N integers, values, where values[i] is the value of node i.
Output
Print a single integer, the maximum sum of values along any root-to-leaf path.
Constraints
1 <= N <= 200000 -10^9 <= values[i] <= 10^9
Example 1
5 -1 0 0 1 1 10 2 -5 3 7
19
Root is 0 with value 10. Paths are 0->1->3 (10+2+3=15), 0->1->4 (10+2+7=19), 0->2 (10-5=5). Max is 19.
Example 2
3 -1 0 0 -1 -2 -3
-3
All values are negative. Paths are 0->1 (-1-2=-3), 0->2 (-1-3=-4). Max is -3.
Hints
Similar problems
- Lexicographically Smallest PathMedium
- Maximum Sum of Non-overlapping SubarraysMedium
- Longest Palindromic SubsequenceMedium
- Maximum Sum Increasing SubsequenceMedium
- Maximum Sum of Non-Overlapping Positive SubarraysMedium
- Longest Zigzag SubsequenceMedium
More topics: Dynamic Programming problems, Trees problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 -1 0 0 1 1 10 2 -5 3 7
3 -1 0 0 -1 -2 -3