题目背景

upd : [2025/1/27] Hack 数据已添加。

某人把 LCA 板子写挂了，然后就有了这道题。

题目描述

有一颗 $n$ 个节点的有根树。

定义 FakeLCA 函数代码如下：

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

其中 fa[i] 表示节点 $i$ 的父节点，特别的，根的父节点是根本身。

现在给定节点数 $n$ 和每个节点的父节点，问有多少个有序数对 $(u,v)$，满足 $1\le u,v\le n$ 且 FakeLCA(u, v) 的结果是 $u$ 和 $v$ 的真正的最近公共祖先。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的父节点。

输出格式

一行一个数表示答案。

1
1

1

5
1 1 1 2 2

21

10
1 1 1 2 2 3 3 3 4 4

78

20
1 1 2 2 2 2 2 4 4 4 4 3 3 3 4 4 7 7 9 10

190

50
1 1 1 1 1 1 1 1 1 2 2 3 4 3 3 4 5 7 2 4 4 3 2 4 6 9 3 8 7 6 12 13 2 12 5 28 17 27 20 36 5 3 2 8 7 6 5 47 26 1

2336

提示

提示：请仔细阅读题目中关于根的说明，根节点不一定是 1 号点！

本题采用捆绑测试。

对于所有数据，$1\le n\le 10^6$。