25489번 - 반짝반짝 3 스페셜 저지

문제

국렬이는 작년 여름에 사용하다 남은 전구 스트립을 이용해서 자신의 자취방에 있는 $N$개의 정점으로 이루어진 트리를 장식하려고 한다.

전구는 트리의 각 정점에 하나씩 설치되어 있다. $i$번째 정점에 붙어있는 전구는 전원을 넣었을 때 $p_i$의 확률로 켜진다. 그리고 전구에 여유가 넘치는 국렬이는 간선에 추가 전구를 하나씩 달았다. 이 추가 전구들은 연결된 두 정점에 설치된 전구들 중 하나만이 켜졌을 때 불이 켜진다.

추가로 국렬이는 $Q$번 특정 정점에 설치된 전구를 다른 전구로 바꿀 것이다. 각 시점별로 불이 들어오는 전구 개수의 기댓값을 구하여라.

입력

첫 번째 줄에는 정점의 개수 $N$이 주어진다. (2ドル \le N \le 500,000円$)

두 번째 줄에는 $p_1$부터 $p_N$이 주어진다. 이는 정확히 소수점 아래 두 자리까지 주어진다. (0ドル.00 \le p_i \le 1.00$)

세 번째 줄부터 $(N+1)$번째 줄까지 두 정수 $u,ドル $v$가 주어진다. 이는 주어진 트리에 정점 $u$와 정점 $v$를 연결하는 간선을 의미한다. (1ドル \le u,v \le N,ドル $u \ne v$)

$(N+2)$번째 줄에는 전구를 바꾸는 횟수를 의미하는 $Q$가 주어진다. (1ドル \le Q \le 500,000円$)

그다음 $Q$개의 줄에 걸쳐서 양의 정수 $u$와 음이 아닌 실수 $p$가 주어진다. 이는 정점 $u$에 설치된 전구를 켜질 확률이 $p$인 전구로 교체하는 것을 의미한다. $p$는 정확히 소수점 아래 두 자리까지 주어진다. (1ドル \le u \le N,ドル 0ドル.00 \le p \le 1.00$)

출력

첫 번째 줄에는 초기의 불이 들어오는 전구의 기댓값을 출력한다. 그다음 $Q$개의 줄에 걸쳐서 각 시점별로 불이 들어오는 전구 개수의 기댓값을 출력한다. 출력한 값과 정답과의 절대 오차 또는 상대 오차가 10ドル^{-6}$ 이하여야 한다.

제한

힌트