Vito는 1부터 n까지 번호가 매겨진 n개의 공원이 있는 도시에 살고 있습니다. 이 공원들은 어떤 두 공원 간에도 경로가 있는 방식으로 n - 1개의 도로로 연결되어 있습니다. 각각의 공원은 아름다움 값이 있으며, i번째 공원의 아름다움 값은 vi입니다.

어젯밤 Vito는 도시 주변을 방황하기로 결정했습니다. 공원을 방문한 후에는 같은 확률로 무작위 도로를 선택하고 해당 도로가 이끄는 공원을 방문합니다. 그러나 여정을 시작하기 전에 그는 자신의 고층 건물 창문을 통해 내다보았고 모든 도로에는 파란색 또는 빨간색 뱀이 있다는 것을 알아냈습니다. 파란색 뱀은 낮은 레이블의 공원에서 높은 레이블의 공원으로 이동하는 모든 사람을 공격하고, 빨간색 뱀은 높은 레이블의 공원에서 낮은 레이블의 공원으로 이동하는 모든 사람을 공격합니다. Vito는 뱀에게 공격당하고 싶지 않기 때문에 임의의 도로를 선택할 때 뱀에게 공격받지 않을 도로만 고려하고자 계획을 바꾸기로 했습니다. 그는 긴 산책을 좋아하므로 적어도 하나의 안전한 도로가 있는 경우에만 여정을 멈추기로 했습니다.

Vito는 자신의 고층 건물의 계단을 내려가면서 어떤 도로에 빨간색 또는 파란색 뱀이 있는지 완전히 잊어버렸기 때문에 그는 궁금해졌습니다. 모든 도로에 파란색 또는 빨간색 뱀이 나타날 확률이 동일하다면, i번째 공원에서 시작하는 내 여정의 기대 아름다움은 무엇일까요?

경로의 아름다움은 해당 여정에서 방문한 공원들의 아름다움 값의 합입니다. 여정의 기대 아름다움은 각각의 가능한 경로에 대한 해당 경로의 아름다움 값과 Vito가 그 경로를 선택할 확률의 곱의 합으로 정의됩니다.

#6186 upload - done - how_to_reg - call_split Subtask stop_circle Grading on hold

공원의 경로 timer 1s memory 32MB

#6186
Subtask

Grading on hold

공원의 경로 1s 32MB