在星际帝国 Bubbledom 中有 $$$N$$$ 个行星,其中一些对通过双向虫洞直接连接。有 $$$N-1$$$ 个虫洞。虫洞在泡泡王国中具有极其重要的宗教意义,泡泡王国中的一组行星认为自己是一个星际王国,当且仅当该组中的任何两个行星可以通过穿越虫洞相互到达时。你知道泡沫王国是一个王国。换句话说,行星和虫洞的网络是一棵树。
然而,Bubbledom 面临着同样拥有传送技术的强大敌人。敌人每晚都会发动攻击,而泡泡政府则在白天夺回所有行星。在一次攻击中,敌人会同时攻击 Bubbledom 的每个星球,但有些星球比其他星球更有弹性。行星编号为$$$0,1,…,N-1$$$,行星$$$i$$$将以$$$p_i$$$的概率掉落。每天晚上之前(包括第一个晚上),政府都会加强或削弱单个星球的防御。
Bubbledom政府对以下问题感兴趣:在一次敌人攻击后(在他们有机会重建之前),Bubbledom预计将分裂成多少个星际王国?换句话说,您需要在每次攻击后打印预期的连接组件数量。
输入
第一行包含一个整数 $$$N$$$ ($$$1 \le N \le 10^5$$$) 表示 Bubbledom 中行星的数量(编号从 $$$0$$$ 到 $$$N-1$$$)。
下一行包含$$$N$$$区间$$$[0,1]$$$内的不同实数,指定小数点后2位,表示相应行星坠落的概率。
接下来的 $$$N-1$$$ 行包含 Bubbledom 中的所有虫洞,其中虫洞由它连接的两个行星指定。
下一行包含一个正整数$$$Q$$$ ($$$1 \le Q \le 10^5$$$),表示敌人攻击的次数。
接下来的 $$$Q$$$ 行每行包含一个非负整数和一个区间 $$$[0,1]$$$ 的实数,表示 Bubbledom 政府决定加强或削弱的行星,以及行星坠落的新概率。
输出
输出包含 $$$Q$$$ 数字,每个数字代表每次敌人攻击后剩余的预期王国数量。如果您的答案的绝对或相对误差不超过 $$$10^{-4}$$$,则视为正确。
示例
输入 #1
5 0.50 0.29 0.49 0.95 0.83 2 3 0 3 3 4 2 1 3 4 0.66 1 0.69 0 0.36
输出 #1
1.68040 1.48440 1.61740