← 返回题目列表

AtCoder · abc357_e

H. 函数图中的可达性

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

有一个有向图 N 顶点编号 1 to N 和 N 边缘。
每个顶点的出度为 1,以及来自顶点的边 i 指向顶点 a_i.
计算顶点对的数量 (u, v) 使得顶点 v 可从顶点到达 u.

这里,顶点 v 可从顶点到达 u 如果存在顶点序列 w_0, w_1, \dots, w_K 长度 K+1 满足以下条件。特别是,如果 u = v,它始终可达。

  • w_0 = u.
  • w_K = v.
  • 对于每个 0 \leq i \lt K,从顶点有一条边 w_i 到顶点 w_{i+1}.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq a_i \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 \dots a_N

输出

打印顶点对的数量 (u, v) 使得顶点 v 可从顶点到达 u.


示例输入 1

4
2 1 1 4

示例输出 1

8

从顶点可到达的顶点 1 是顶点 1, 2.
从顶点可到达的顶点 2 是顶点 1, 2.
从顶点可到达的顶点 3 是顶点 1, 2, 3.
从顶点可到达的顶点 4 是顶点 4.
因此,顶点对的数量 (u, v) 使得顶点 v 可从顶点到达 u is 8.
请注意,来自顶点的边 4 是一个自循环,即指向顶点 4 本身。


示例输入 2

5
2 4 3 1 2

示例输出 2

14

示例输入 3

10
6 10 4 1 5 9 8 6 5 1

示例输出 3

41