Description：

给一棵树，每个点被充电有概率，每条边导电有概率，问有电的点的个数的期望。

$1\le n \le 500000$

Solution：

首先答案 $\begin{align}=\sum_{i=1}^n\end{align}$ $i$ 号点有电的概率。

然后关键问题就是如何求这个点有电的概率，每个点有三种可能，他自己被充电，他父亲通过一条边给他充电，儿子给他充电，这个点没有电当且仅当所有这些路都没电，既然是一棵树，而且每个点又和父亲节点有关，很有可能是二次扫描与换根，如果计算有电式子会变得很繁琐，但不是不能推，设 $f[i]$ 表示这个点不由它或它儿子供上电的概率， $\begin{align}f[i]=\prod_{j\ is\ child}(f[j]+(1-f[j])\times (1-p[(i,j)]))\times (1-p[i])\end{align}$ ，然后再换根，设 $g[]$ 表示这个点没被供上电的概率， $g[1]=f[1]$ ， $x=\frac{g[fa[i]]}{(f[i]+(1-f[i])\times (1-p[(i,fa[i])]))}$ ， $g[i]=f[i]\times(x+(1-x)\times (1-p[(fa[i],i)]))$ ，最后把所有 $1-g[i]$ 累加起来即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 500010

double pp[MAXN];

struct edge

{

	int to,nxt;

	double p;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,double p)

{

	++edgenum;e[edgenum].to = b;e[edgenum].p = p;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].p = p;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

bool vis[MAXN];

double f[MAXN],g[MAXN];

void dp1(int k)

{

	vis[k] = true;

	f[k] = 1.0 - pp[k];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dp1(e[i].to);

		f[k] *= f[e[i].to] + (1.0 - f[e[i].to]) * (1.0 - e[i].p);

	}

	return;

}

void dp2(int k)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		double x = g[k] / (f[e[i].to] + (1.0 - f[e[i].to]) * (1.0 - e[i].p));

		g[e[i].to] = f[e[i].to] * (x + (1.0 - x) * (1.0 - e[i].p));

		dp2(e[i].to);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	int a,b,p;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%d",&a,&b,&p);

		add(a,b,(double)p / 100.0);

	}

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&p);

		pp[i] = (double)p / 100.0;

	}

	dp1(1);

	g[1] = f[1];

	memset(vis,false,sizeof(vis));

	dp2(1);

	double ans = 0;

	for(int i = 1;i <= n;++i)

		ans += 1.0 - g[i];

	printf("%.6lf\n",ans);

	return 0;

}