Maximum Depth Sum of Unique Paths
Given a tree represented by a parent array, where parent[i] is the parent of node i and parent[0] == -1 indicates node 0 is the root. For each node u, calculate the sum of depths of all nodes in its subtree, including u itself. The depth of the root (node 0) is 0. Return the maximum such sum among all nodes.
Input
The first line contains an integer N, the number of nodes. The second line contains N integers, the parent array. parent[i] is the parent of node i.
Output
Print a single integer, the maximum sum of depths of nodes in any subtree.
Constraints
1 <= N <= 200000. The input represents a valid tree.
Example 1
5 -1 0 0 1 1
6
Tree: 0 is root, children 1, 2. Node 1 children 3, 4. Depths: d(0)=0, d(1)=1, d(2)=1, d(3)=2, d(4)=2. Subtree sums: S(0)=0+1+1+2+2=6, S(1)=1+2+2=5, S(2)=1, S(3)=2, S(4)=2. Max sum is 6.
Example 2
7 -1 0 0 1 1 2 2
10
Tree: 0->{1,2}, 1->{3,4}, 2->{5,6}. Depths: d(0)=0, d(1)=1, d(2)=1, d(3)=2, d(4)=2, d(5)=2, d(6)=2. Subtree sums: S(0)=0+1+1+2+2+2+2=10, S(1)=1+2+2=5, S(2)=1+2+2=5, S(3)=2, S(4)=2, S(5)=2, S(6)=2. Max sum is 10.
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