Trận chiến liên hành tinh

Có $N$ hành tinh được đánh số từ $0$ đến $N-1$, nối với nhau bởi $N-1$ đường hầm hai chiều sao cho từ bất kì hành tinh nào cũng có thể đi đến mọi hành tinh khác. Nói cách khác, mạng lưới hành tinh tạo thành một cây.

Mỗi đêm, kẻ địch tấn công đồng thời tất cả các hành tinh. Hành tinh $i$ sẽ thất thủ với xác suất $p_i$ (độc lập với các hành tinh khác). Sau cuộc tấn công, một số hành tinh bị mất; các hành tinh còn trụ lại cùng những đường hầm nối giữa chúng chia mạng lưới thành các thành phần liên thông — hai hành tinh thuộc cùng một thành phần nếu có thể đi từ hành tinh này tới hành tinh kia chỉ qua các hành tinh còn trụ.

Trước mỗi đêm (kể cả đêm đầu tiên), chính phủ thay đổi xác suất thất thủ của đúng một hành tinh. Sau mỗi lần thay đổi đó, hãy tính kì vọng số thành phần liên thông còn lại sau một cuộc tấn công.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$ — số hành tinh.
• Dòng thứ hai chứa $N$ số thực trong đoạn $[0,1]$, mỗi số có đúng $2$ chữ số sau dấu chấm thập phân, là các xác suất thất thủ $p_0,p_1,\dots ,p_{N-1}$.
• $N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một đường hầm nối hai hành tinh.
• Dòng tiếp theo chứa số nguyên $Q$ — số lần tấn công.
• $Q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $u$ và một số thực $x$ (có $2$ chữ số thập phân): gán $p_u=x$.

Dữ liệu ra

Gồm $Q$ dòng, dòng thứ $i$ là kì vọng số thành phần liên thông sau lần tấn công thứ $i$. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-4}$.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le Q\le {10}^5$
• $0\le p_i\le 1$

Ví dụ