Chain Square

Problem Statement

Chain Square Given a directed tree of N nodes in a form of an array A of size N - 1 , such that there is a directed edge from the node A[i] to the node i+1 ( 1 ≤ i < N ). You can perform the following operations on it: In one operation, you can break any edge in the tree, dividing that tree into two trees. Break the given tree into a set of trees such that each tree is a directed chain. Your score is the sum of squares of lengths of the directed chains in the set. Print the maximum possible score. Notes A directed chain is a directed tree such that each node in that tree has at most one out-degree and at most one in-degree . The length of a directed chain is the number of nodes in that directed chain. Assume 1 -based indexing. Input Format The first line contains an integer N , representing the size of the tree. The second line contains N - 1 space-separated integers representing the array A . Output Format Print a single integer representing the maximum possible score. Constraints