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

输入 #1

4
2 1 1 4

输出 #1

8

输入输出样例 #2

输入 #2

5
2 4 3 1 2

输出 #2

14

输入输出样例 #3

输入 #3

10
6 10 4 1 5 9 8 6 5 1

输出 #3

41

说明/提示

限制条件

• $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 翻译