著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”
SHOI概率充电器由n-1条导线连通了n个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为SHOI公司的忠实客户,你无法抑制自己购买SHOI产品的冲动。在排了一个星期的长队之后终于入手了最新型号的SHOI概率充电器。你迫不及待地将SHOI概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?
第一行一个整数:n。概率充电器的充电元件个数。充电元件由1-n编号。
之后的n-1行每行三个整数a, b, p,描述了一根导线连接了编号为a和b的充电元件,通电概率为p%。
第n+2行n个整数:qi。表示i号元件直接充电的概率为qi%。
【数据规模】
对于30%的数据,n≤5000。
对于100%的数据,n≤500000,0≤p,qi≤100。
输出一行一个实数,为能进入充电状态的元件个数的期望,四舍五入到小数点后6位小数。
charger1.in
|
charger1.out
|
3
1 2 50
1 3 50
50 0 0
|
1.000000
|
charger2.in
|
charger2.out
|
5
1 2 90
1 3 80
1 4 70
1 5 60
100 10 20 30 40
|
4.300000
|