← 返回题目列表

Codeforces · 1045/D

D. 星际战斗

中文机器翻译题面 查看原题

在星际帝国 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