#P3566. [SHOI2014]概率充电器

    ID: 2764 传统题 2000ms 256MiB 尝试: 2193 已通过: 787 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划换根 DP概率 DP前后缀合并排除子节点概率与期望指示变量期望线性性补事件计算CF2200

[SHOI2014]概率充电器

[SHOI2014] 概率充电器

题目描述

著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:

“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”

SHOI 概率充电器由 n−1n-1 条导线连通了 nn 个充电元件。进行充电时,每条导线是否导电、每个元件是否直接充电均按给定概率独立决定。电能可以从直接充电的元件经由导电的连通路径传到其他元件。

作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?

输入格式

第一行一个整数 nn。概率充电器的充电元件个数。充电元件由 1∼n1 \sim n 编号。

之后的 n−1n-1 行每行三个整数 a,b,pa, b, p,描述了一根导线连接了编号为 aa 和 bb 的充电元件,通电概率为 p%p\%。

最后一行(第 n+1n+1 行)有 nn 个整数 q1,…,qnq_1,\ldots,q_n。其中 qi%q_i\% 是 ii 号元件直接充电的概率。

输出格式

输出一行一个实数,为能进入充电状态的元件个数的期望,四舍五入到小数点后 6 位小数。

样例 #1

3
1 2 50
1 3 50
50 0 0
1.000000

样例 #2

5
1 2 90
1 3 80
1 4 70
1 5 60
100 10 20 30 40
4.300000

数据范围

对于 30%30\% 的数据,n≤5×103n \leq 5 \times 10^3。

对于 100%100\% 的数据,n≤5×105n \leq 5 \times 10^5,0≤p,qi≤1000 \leq p,q_i \leq 100。