Find Longest Path to Leaf
You are given a rooted tree represented by a parent array. The parent of the root is -1. All nodes are numbered from 0 to N-1, where 0 is the root. Calculate the length of the longest path from any node in the tree to any leaf node in its subtree. The path length is defined as the number of edges.
Input
The first line contains an integer N (2 <= N <= 200000), the number of nodes in the tree. The second line contains N integers, where the i-th integer is the parent of node i. The parent of the root (node 0) is -1.
Output
Print a single integer, the length of the longest path from any node to a leaf in its subtree.
Constraints
2 <= N <= 200000 Parents are integers in the range [-1, N-1]. Node 0 is the root, its parent is -1. Exactly one node has parent -1. There are no cycles.
Example 1
5 -1 0 0 1 1
2
Tree: 0 is root, children 1, 2. Node 1 has children 3, 4. Node 2 is a leaf. Node 3, 4 are leaves. Longest path is 0 -> 1 -> 3 (or 4), length 2.
Example 2
7 -1 0 0 1 1 2 2
2
Tree: 0 root, children 1, 2. Node 1 children 3, 4. Node 2 children 5, 6. All 3,4,5,6 are leaves. Longest path from node 0 to leaf is 0->1->3 (length 2). Longest path from node 1 to leaf is 1->3 (length 1). Longest path from node 2 to leaf is 2->5 (length 1). Max overall is 2.
Hints
# 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
7 -1 0 0 1 1 2 2