/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 450 点
問題文
頂点に 1 から N の番号がついた N 頂点 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 \lt K を満たす全ての i について、頂点 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) であって、頂点 u から頂点 v へ到達可能であるものの個数を出力せよ。
入力例 1
4 2 1 1 4
出力例 1
8
頂点 1 から到達可能である頂点は頂点 1, 2 です。
頂点 2 から到達可能である頂点は頂点 1, 2 です。
頂点 3 から到達可能である頂点は頂点 1, 2, 3 です。
頂点 4 から到達可能である頂点は頂点 4 のみです。
よって、頂点の組 (u, v) であって頂点 u から頂点 v へ到達可能であるものの個数は 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
Score : 450 points
Problem Statement
There is a directed graph with N vertices numbered 1 to N and N edges.
The out-degree of every vertex is 1, and the edge from vertex i points to vertex a_i.
Count the number of pairs of vertices (u, v) such that vertex v is reachable from vertex u.
Here, vertex v is reachable from vertex u if there exists a sequence of vertices w_0, w_1, \dots, w_K of length K+1 that satisfies the following conditions. In particular, if u = v, it is always reachable.
- w_0 = u.
- w_K = v.
- For every 0 \leq i \lt K, there is an edge from vertex w_i to vertex w_{i+1}.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq a_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N a_1 a_2 \dots a_N
Output
Print the number of pairs of vertices (u, v) such that vertex v is reachable from vertex u.
Sample Input 1
4 2 1 1 4
Sample Output 1
8
The vertices reachable from vertex 1 are vertices 1, 2.
The vertices reachable from vertex 2 are vertices 1, 2.
The vertices reachable from vertex 3 are vertices 1, 2, 3.
The vertex reachable from vertex 4 is vertex 4.
Therefore, the number of pairs of vertices (u, v) such that vertex v is reachable from vertex u is 8.
Note that the edge from vertex 4 is a self-loop, that is, it points to vertex 4 itself.
Sample Input 2
5 2 4 3 1 2
Sample Output 2
14
Sample Input 3
10 6 10 4 1 5 9 8 6 5 1
Sample Output 3
41