Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem J:
Black Company

JAG Company is a sweatshop (sweatshop is called "burakku kigyo" in Japanese), and you are
the CEO for the company.

You are planning to determine $N$ employees' salary as low as possible (employees are numbered
from 1 to $N$). Each employee's salary amount must be a positive integer greater than zero. At
that time, you should pay attention to the employees' contribution degree. If the employee $i$'s
contribution degree $c_i$ is greater than the employee $j$'s contribution degree $c_j$ , the employee i
must get higher salary than the employee $j$'s salary. If the condition is not satisfied, employees
may complain about their salary amount.

However, it is not necessarily satisfied in all pairs of the employees, because each employee can
only know his/her close employees' contribution degree and salary amount. Therefore, as long as
the following two conditions are satisfied, employees do not complain to you about their salary
amount.

 If the employees $i$ and $j$ are close to each other, $c_i < c_j \Leftrightarrow  p_i < p_j$ must be satisfied, where
$p_i$ is the employee $i$'s salary amount.

 If the employee $i$ is close to the employees $j$ and $k$, $c_j < c_k \Leftrightarrow  p_j < p_k$ must be satisfied.
Write a program that computes the minimum sum of all employees' salary amount such that no
employee complains about their salary.

Input

Each input is formatted as follows:

$N$

$c_1$ ... $c_N$

$M$

$a_1$ $b_1$

...

$a_M$ $b_M$

The first line contains an integer $N$ ($1 \leq N \leq 100,000$), which indicates the number of employees.
The second line contains $N$ integers $c_i$ ($1 \leq c_i \leq 100,000$) representing the contribution degree
of employee $i$.

The third line contains an integer $M$ ($0 \leq M \leq 200,000$), which specifies the number of relationships. Each of the following $M$ lines contains two integers $a_i$ and $b_i$ ($a_i \ne b_i, 1 \leq a_i, b_i \leq N$).
It represents that the employees $a_i$ and $b_i$ are close to each other. There is no more than one
relationship between each pair of the employees.

Output

Print the minimum sum of all employees' salary amounts in a line.

Sample Input

3
1 3 3
2
1 2
1 3

Output for the Sample Input

5

Sample Input

3
1 2 3
2
1 2
1 3

Output for the Sample Input

6

Sample Input

4
1 1 2 2
2
1 2
3 4

Output for the Sample Input

4

Sample Input

5
1 2 5 5 1
6
1 2
4 1
2 3
5 2
4 3
4 5

Output for the Sample Input

10

Sample Input

6
4 3 2 1 5 3
7
4 2
1 5
2 6
6 5
4 1
1 6
6 3

Output for the Sample Input

13



Sample input:
3
1 3 3
2
1 2
1 3


Sample output:
5

Submission status: Accepted

Solution code:
from collections import deque
import sys
def main():
    readline = sys.stdin.readline
    write = sys.stdout.write
    def root(x):
        if x == p[x]:
            return x
        p[x] = y = root(p[x])
        return y
    def unite(x, y):
        px = root(x)
        py = root(y)
        if px < py:
            p[py] = px
        else:
            p[px] = py

    N = int(readline())
    *C, = map(int, readline().split())
    M = int(readline())
    *p, = range(N)
    G = [[] for i in range(N)]
    G0 = [[] for i in range(N)]
    for i in range(M):
        a, b = map(int, readline().split()); a -= 1; b -= 1
        G[a].append(b)
        G[b].append(a)
        ca = C[a]; cb = C[b]
        if ca < cb:
            G0[a].append(b)
        elif cb < ca:
            G0[b].append(a)
    for v in range(N):
        ws = G[v]
        if not ws:
            continue
        ws.sort(key = C.__getitem__)
        c = C[v]
        prv = ws[0]; pw = C[prv]
        if C[prv] == c:
            unite(v, prv)
        for w in ws[1:]:
            cw = C[w]
            if pw == cw:
                unite(prv, w)
            else:
                G0[prv].append(w)
            if cw == c:
                unite(v, w)
            prv = w; pw = cw

    G1 = [[] for i in range(N)]
    deg = [0]*N
    for v in range(N):
        pv = root(v)
        for w in G0[v]:
            pw = root(w)
            if pv != pw:
                G1[pv].append(pw)
                deg[pw] += 1

    que = deque()
    D = [0]*N
    for i in range(N):
        if root(i) != i:
            continue
        if deg[i] == 0:
            que.append(i)
            D[i] = 1
    while que:
        v = que.popleft()
        d = D[v]
        for w in G1[v]:
            deg[w] -= 1
            if deg[w] == 0:
                que.append(w)
            D[w] = max(D[w], d+1)
    for i in range(N):
        if root(i) == i:
            continue
        D[i] = D[root(i)]
    write("%d\n" % sum(D))
main()