BZOJ3566 [SHOI2014]概率充电器 概率+树形DP

发布于 2017-09-13  4.53k 次阅读


[toggle hide="yes" title="题目" color=""]

Description

著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!

SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。
你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?

Input

第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。
之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的
充电元件,通电概率为 p%。
第 n+2 行 n 个整数:qi。表示 i 号元件直接充电的概率为 qi%。

Output

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

Sample Input

3
1 2 50
1 3 50
50 0 0

Sample Output

1.000000

HINT

对于 100%的数据,n≤500000,0≤p,qi≤100。

[/toggle]

对现在来说算是非常难的DP,这样计算感觉很不好想啊,但是思路其实很清晰。

首先,这题要求的其实就是每个点被充电的概率,但如果正着推会很复杂,因为充电的情况比较多,所以我们计算每个点不被充电的概率。

假设我们目前在计算点i的值,那么把树划分成三个部分:i的父节点及以上部分,i以及i的子树,i的兄弟节点及其子树。

设f[i]表示i不被自身或是i的子树充电的概率,g[i]表示i不被i的父亲节点充电的概率,那么f[i]*g[i]即为i不被充电的概率,q[i]表示i不被自身充电的概率,将边权也都变成不导电的概率。

先来计算f[i]:考虑i不被自身或是子树充电的条件:

1.i自身不发电。

2.i的子节点没电或者有电但是与i的边不通(这种情况以及保证i没电,所以子节点肯定不会被i充电,可以直接利用子节点的f值)。

这样,我们就可以得到f[i]的式子:

$$f[i]= q[i] * \prod ( f[son[i]] + (1 - f[son[i]]) * e[i].w)$$

 

接着来计算g[i]:考虑i不被父节点充电的条件:

1.i的父亲带电,但是边不通。

2.i的父亲不带电(fa[i]既不被fa[fa[i]]充电,又不被除i以外的子树充电,但是要排除i的影响,防止和f[i]重复考虑)

计算父亲不被充电的概率:$$P=g[fa[i]]*f[fa[i]]/(f[i]+(1-f[i])*e[i<-->fa[i]].w)$$

这样,我们就可以得到g[i]的式子:$$g[i]=P+(1-P)*e[i<-->fa[i]].w$$

代码实现上,f值可以递归算完子树之后在计算当前点的值,而g值反过来算比较好。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974