BOJ 16297 Eating Everything Efficiently

문제 링크:

문제 내용

마가렛은 지금 피자 축제에 와 있습니다. 이 축제에는 $n$개의 피자 가게가 $m$개의 단방향 통로로 연결되어 있으며, 사이클은 존재하지 않습니다. 모든 피자 가게는 $0$번 피자 가게로부터 직접 또는 간접적으로 연결되어 있습니다.

마가렛은 피자를 2판까지밖에 먹지 못하지만, 다음의 전략을 사용하여 많은 피자들을 맛보려고 합니다.

• 맨 처음 먹을 피자는 1판을 모두 먹습니다. 다음 피자는 $\left\lfloor \frac{1}{2} \right\rfloor$판을 먹고, 그 다음 피자는 $\left\lfloor \frac{1}{4} \right\rfloor$판을 먹고, … $i$번째 피자는 $\left\lfloor \frac{1}{2^{i-1}} \right\rfloor$판을 먹습니다.

마가렛은 축제장 밖으로 나갈 때까지 만나는 각각의 피자에 대해 먹을지 말지를 선택할 수 있습니다. 마가렛은 피자를 먹을 때마다 그 피자의 맛과 그 피자를 먹은 양을 곱한 값만큼의 만족감을 얻습니다. 만족감의 합의 최댓값을 구하세요.

입력

첫 번째 줄에는 피자 가게의 수 $n$과 통로의 개수 $m$이 주어집니다. ($1 \le n \le 500\;000$, $0 \le m \le 500\;000$)

두 번째 줄에는 0번, 1번, …, $n-1$번 피자 가게에서 먹을 수 있는 피자의 맛 $c_0, c_1, \cdots, c_{n-1}$이 주어집니다. 이들은 음이 아닌 정수입니다. ($0 \le c_i \le 10^9$)

다음 $m$줄 각각에는 각 통로의 시작점 $s$와 끝점 $t$가 주어집니다. ($0 \le s, t < n$, $s \neq t$) 같은 쌍은 여러 번 주어지지 않습니다.

출력

마가렛이 얻을 수 있는 만족감의 합의 최댓값을 출력합니다. 정답과의 절대 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정됩니다.

문제 풀이