C - Sum on Blackboard
Benihuki
2
s
1024
MB
150
点
問題文
黒板に $N$ 個の整数 $A_1, \cdots, A_N$ が書かれています。
あなたは次の $Q$ 回の操作を順に行います。
- $i$ 回目の操作では、黒板に整数 $X_i$ が書かれていれば、それらをすべて $Y_i$ に書き換える。
$Q$ 回の操作を終えた後の、黒板に書かれている整数の総和を求めてください。
答えは $32$ bit整数型に収まらない可能性があります。
制約
- $1 \leq N \leq 10^5$
- $0 \leq Q \leq 10^5$
- $0 \leq A_i \leq 10^5\ (1 \leq i \leq N)$
- $0 \leq X_i, Y_i \leq 10^5\ (1 \leq i \leq Q)$
- $X_i \neq Y_i$
- 入力はすべて整数
入力
入力は標準入力から以下の形式で与えられる。
$N$ $Q$
$A_1\ A_2\ \dots\ A_N$
$X_1\ Y_1$
$\vdots$
$X_Q\ Y_Q$
出力
$Q$ 回の操作後の、黒板に書かれている整数の総和を出力してください。
入力例 1
3 3
1 2 3
1 2
2 3
3 4
出力例 1
12
$1$ 回目の操作で、整数は ${1, 2, 3} \to {2, 2, 3}$ と書き換えられます。
$2$ 回目の操作で、整数は ${2, 2, 3} \to {3, 3, 3}$ と書き換えられます。
$3$ 回目の操作で、整数は ${3, 3, 3} \to {4, 4, 4}$ と書き換えられます。
入力例 2
8 9
2 0 1 9 1 2 3 0
1 404
2 404
3 404
4 0
5 0
6 0
7 0
8 0
9 0
出力例 2
2020