分数: 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