Counting Correct FakeLCA Pairs in a Rooted Tree

Given a rooted tree with n nodes (numbered from 1 to n), each node has a parent pointer fa[i] (for 1 ≤ i ≤ n) with the special property that the root’s parent is the root itself. We define a function FakeLCA(u, v) as follows:

int FakeLCA(int u, int v) {
    while(u != v) {
        u = fa[u];
        v = fa[v];
    }
    return u;
}

The true lowest common ancestor (LCA) of two nodes in a tree is the deepest (i.e. furthest from the root) node that is an ancestor of both. Your task is to count the number of ordered pairs (u, v) (1 ≤ u, v ≤ n) such that the result of FakeLCA(u, v) is equal to the true LCA(u, v) of nodes u and v.

Observation and Hint: A careful analysis shows that the FakeLCA algorithm gives the correct answer in two cases:

• When both nodes u and v have the same depth.
• When the true LCA(u, v) is the root. (Recall that the root's parent is itself.)

It can be proved that the final answer can be computed by the formula:

[ \text{answer} = n^2 - \sum_{c\in Child(root)} \text{size}(c)^2 + \sum_{c\in Child(root)} \left(\sum_{d\ge0} \text{subtreeCount}_c(d)^2\right), ]

where for each child c of the root, size(c) is the number of nodes in the subtree rooted at c and subtreeCountc(d) is the number of nodes in that subtree at relative depth d (with the child itself at depth 0).

Your program should build the tree from the given parent pointers and output the computed number.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of nodes in the tree.

The second line contains n integers: fa[1], fa[2], ..., fa[n]. It is guaranteed that for the root node r, fa[r] = r.

outputFormat

Output a single integer – the number of ordered pairs (u, v) (1 ≤ u, v ≤ n) such that FakeLCA(u, v) equals the true LCA(u, v).

sample

3
1 1 1

9