AT_abc357_e.[ABC357E] Reachability in Functional Graph

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个有 $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
```
4
2 1 1 4
```
输出#1
```
8
```
输入#2
```
5
2 4 3 1 2
```
输出#2
```
14
```
输入#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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页