函数图中的可达性

题目描述

有一个顶点编号为 $1$ 到 $N$、共有 $N$ 条边的有向图。

每个顶点的出度都是 $1$，从顶点 $i$ 出发的边指向顶点 $a_i$。

求满足「从顶点 $u$ 可以到达顶点 $v$」的顶点对 $(u, v)$ 的数量。

这里，如果存在长度 $K+1$ 的顶点序列 $w_0, w_1, \dots, w_K$ 满足以下条件，则称从顶点 $u$ 可以到达顶点 $v$。特别地，当 $u = v$ 时总是可以到达。

• $w_0 = u$。
• $w_K = v$。
• 对每个 $0 \leq i \lt K$，都存在从顶点 $w_i$ 到顶点 $w_{i+1}$ 的边。

输入格式

输入按以下格式从标准输入给出：

$N$
$a_1$ $a_2$ $\dots$ $a_N$

输出格式

输出满足「从顶点 $u$ 可以到达顶点 $v$」的顶点对 $(u, v)$ 的数量。

样例

4
2 1 1 4

8

从顶点 $1$ 可以到达的顶点是 $1, 2$。

从顶点 $2$ 可以到达的顶点是 $1, 2$。

从顶点 $3$ 可以到达的顶点是 $1, 2, 3$。

从顶点 $4$ 可以到达的顶点是 $4$。

因此，满足条件的顶点对 $(u, v)$ 数量为 $8$。

注意，从顶点 $4$ 出发的边是自环，即指向顶点 $4$ 本身。

5
2 4 3 1 2

14

10
6 10 4 1 5 9 8 6 5 1

41

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq a_i \leq N$
• 输入均为整数