Reachability in Functional Graph

题目描述

有一个有向图，包含编号为 $1$ 到 $N$ 的 $N$ 个顶点和 $N$ 条边。
每个顶点的出度都是 $1$，并且从顶点 $i$ 出发的边指向顶点 $a_i$.
计算顶点对 $(u, v)$ 的数量，使得顶点 $v$ 可以从顶点 $u$ 到达。 这里，当存在满足以下条件的长度为 $K+1$ 的顶点序列 $w_0, w_1, \dots, w_K$ 时，称顶点 $v$ 可以从顶点 $u$ 到达。特别地，如果 $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)$ 的数量，使得顶点 $v$ 可以从顶点 $u$ 到达。

4
2 1 1 4

8

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$ 所有输入值均为整数。从顶点 $1$ 可到达的顶点是顶点 $1, 2$.
从顶点 $2$ 可到达的顶点是顶点 $1, 2$.
从顶点 $3$ 可到达的顶点是顶点 $1, 2, 3$.
从顶点 $4$ 可到达的顶点是顶点 $4$.
因此，使得顶点 $v$ 可以从顶点 $u$ 到达的顶点对 $(u, v)$ 的数量是 $8$.
注意，顶点 $4$ 的边是一个自环，即指向它自身的边。

标签: AtCoder|abc357E

来源

AtCoder|abc357E