Loj #2192. 「SHOI2014」概率充电器

题目描述

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

「采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！SHOI 概率充电器，您生

活不可或缺的必需品！能充上电吗？现在就试试看吧！」

SHOI 概率充电器由 \(n-1\) 条导线连通了 \(n\) 个充电元件。进行充电时，每条导线是否可以导电以

概率决定，每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过

通电的导线使得其他充电元件进行间接充电。

作为 SHOI 公司的忠实客户，你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终

于入手了最新型号的 SHOI 概率充电器。你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想

知道，进入充电状态的元件个数的期望是多少呢？

输入格式

第一行一个整数 \(n\)，概率充电器的充电元件个数，充电元件由 \(1 \sim n\) 编号。

之后的 \(n-1\) 行每行三个整数 \(a, b, p\)，描述了一根导线连接了编号为 \(a\) 和 \(b\) 的充电元

件，通电概率为 \(p\, \%\)。

第 \(n+2\) 行 \(n\) 个整数 \(q_1,\ldots,q_n\)。表示 \(i\) 号元件直接充电的概率为 \(q_i\, \%\)。

输出格式

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

数据范围与提示

对于 \(100\%\) 的数据，\(n \leq 500000,\ 0 \leq p,q_i \leq 100\)。

\(\\\)

根据期望的线性性，我们统计每个点通电出现的概率。发现统计每个点不通电的概率好统计些，也就是该点所在联通块一个点都不通电。

上下两次树形\(DP\)就搞定了。

代码：

#include
    
     #define ll long long#define N 500005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n;struct road {    int to,nxt;    double p;}s[N<<1];int h[N],cnt;void add(int i,int j,double p) {    s[++cnt]=(road) {j,h[i],p};h[i]=cnt;}double f[N];double up[N];double q[N];void dfs(int v,int fr) {    f[v]=1-q[v];    for(int i=h[v];i;i=s[i].nxt) {        int to=s[i].to;        if(to==fr) continue ;        dfs(to,v);        f[v]=f[v]*(s[i].p*f[to]+(1.0-s[i].p));    }}double pre[N],suf[N];double ans;void dfs2(int v,int fr) {    ans+=1.0-f[v]*up[v];    vector
     
      tem;    vector
      
       E;    tem.clear();    E.clear();    for(int i=h[v];i;i=s[i].nxt) {        int to=s[i].to;        if(to==fr) continue ;        tem.push_back(to);        E.push_back(s[i].p);        suf[to]=pre[to]=s[i].p*f[to]+(1.0-s[i].p);    }    for(int i=1;i
       
        =0;i--) suf[tem[i]]=suf[tem[i]]*suf[tem[i+1]];    for(int i=0;i
        
         0) now=now*pre[tem[i-1]];        if(i