{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn the intergalactic empire Bubbledom there are $$$N$$$ planets, of which some pairs are directly connected by two-way wormholes. There are $$$N-1$$$ wormholes. The wormholes are of extreme religious importance in Bubbledom, a set of planets in Bubbledom consider themselves one intergalactic kingdom if and only if any two planets in the set can reach each other by traversing the wormholes. You are given that Bubbledom is one kingdom. \u003cspan class\u003d\"tex-font-style-underline\"\u003eIn other words, the network of planets and wormholes is a tree.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eHowever, Bubbledom is facing a powerful enemy also possessing teleportation technology. The enemy attacks every night, and the government of Bubbledom retakes all the planets during the day. In a single attack, the enemy attacks every planet of Bubbledom at once, but some planets are more resilient than others. Planets are number $$$0,1,…,N-1$$$ and the planet $$$i$$$ will fall with probability $$$p_i$$$. Before every night (including the very first one), the government reinforces or weakens the defenses of a single planet.\u003c/p\u003e\u003cp\u003eThe government of Bubbledom is interested in the following question: what is the expected number of intergalactic kingdoms Bubbledom will be split into, after a single enemy attack (before they get a chance to rebuild)? \u003cspan class\u003d\"tex-font-style-underline\"\u003eIn other words, you need to print the expected number of connected components after every attack.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer number $$$N$$$ ($$$1 \\le N \\le 10^5$$$) denoting the number of planets in Bubbledom (numbered from $$$0$$$ to $$$N-1$$$). \u003c/p\u003e\u003cp\u003eThe next line contains $$$N$$$ different real numbers in the interval $$$[0,1]$$$, specified with 2 digits after the decimal point, denoting the probabilities that the corresponding planet will fall.\u003c/p\u003e\u003cp\u003eThe next $$$N-1$$$ lines contain all the wormholes in Bubbledom, where a wormhole is specified by the two planets it connects.\u003c/p\u003e\u003cp\u003eThe next line contains a positive integer $$$Q$$$ ($$$1 \\le Q \\le 10^5$$$), denoting the number of enemy attacks.\u003c/p\u003e\u003cp\u003eThe next $$$Q$$$ lines each contain a non-negative integer and a real number from interval $$$[0,1]$$$, denoting the planet the government of Bubbledom decided to reinforce or weaken, along with the new probability that the planet will fall.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput contains $$$Q$$$ numbers, each of which represents the expected number of kingdoms that are left after each enemy attack. Your answers will be considered correct if their absolute or relative error does not exceed $$$10^{-4}$$$. \u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n0.50 0.29 0.49 0.95 0.83\n2 3\n0 3\n3 4\n2 1\n3\n4 0.66\n1 0.69\n0 0.36\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1.68040\n1.48440\n1.61740\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}