AT_abc357_e [ABC357E] Reachability in Functional Graph

有一个有 $N$ 个顶点和 $N$ 条边的有向图，顶点编号为 $1$ 到 $N$。 每个顶点的出度都是 $1$，从顶点 $i$ 出发的边指向顶点 $a_i$。 请你求出所有满足从顶点 $u$ 可以到达顶点 $v$ 的顶点对 $(u, v)$ 的个数。 这里，从顶点 $u$ 可以到达顶点 $v$，是指存在一个长度为 $K+1$ 的顶点序列 $w_0, w_1, \dots, w_K$，满足以下所有条件。特别地，当 $u = v$ 时，总是可以到达。 - $w_0 = u$ - $w_K = v$ - 对于所有满足 $0 \leq i < K$ 的 $i$，都存在一条从顶点 $w_i$ 指向顶点 $w_{i+1}$ 的边。

输入按以下格式从标准输入给出。 > $N$ $a_1$ $a_2$ $\dots$ $a_N$

输出所有满足从顶点 $u$ 可以到达顶点 $v$ 的顶点对 $(u, v)$ 的个数。

## 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq a_i \leq N$ - 输入的所有值均为整数 ## 样例解释 1 从顶点 $1$ 可以到达的顶点是顶点 $1, 2$。 从顶点 $2$ 可以到达的顶点是顶点 $1, 2$。 从顶点 $3$ 可以到达的顶点是顶点 $1, 2, 3$。 从顶点 $4$ 只能到达顶点 $4$。 因此，满足条件的顶点对 $(u, v)$ 的个数为 $8$。 注意，从顶点 $4$ 出发的边是自环，即指向顶点 $4$ 自身。 由 ChatGPT 4.1 翻译