class="markdown_views prism-atom-one-light">

题目描述：

QAQ…

题目分析：

P(A+B)=P(A)+P(B)−P(AB)" role="presentation">P(A+B)=P(A)+P(B)−P(AB)$P(A+B)=P(A)+P(B)-P(AB)$
首先可以将元件能否充电分成3种情况考虑 1、它自己给自己充好了电 2、它的儿子方向给它传送了电 3、它的父亲方向给它传送了电。 1 是输入的
2 可以通过一次dfs做
3 麻烦一点，因为2中我们已经求得当前点(now)的儿子们给当前点的贡献，现在要求当前点给它的某个儿子(to)的贡献，这里要计算的话，就必须要排除之前to->now的，（想想若2中计算了to->now的概率，现在又要计算now->to的概率，明显出现了循环） 设y = now点除了从to点来的电 的充电概率，dp[i]表示i点的充电概率，pson[i]表示在i的子树中，i的充电概率
pson[to]∗p+y−pson[to]∗p∗y=dp[now]" role="presentation">pson[to]∗p+y−pson[to]∗p∗y=dp[now]$$pson[to]\ast p+y-pson[to]\ast p\ast y=dp[now]$$
(1−pson[to]∗p)∗y=dp[now]−pson[to]∗p" role="presentation">(1−pson[to]∗p)∗y=dp[now]−pson[to]∗p$$(1-pson[to]\ast p)\ast y=dp[now]-pson[to]\ast p$$
y=(dp[now]−pson[to]∗p)/(1−pson[to]∗p);" role="presentation">y=(dp[now]−pson[to]∗p)/(1−pson[to]∗p);$$y=(dp[now]-pson[to]\ast p)/(1-pson[to]\ast p);$$
dp[to]=pson[to]+y∗p−pson[to]∗y∗p;" role="presentation">dp[to]=pson[to]+y∗p−pson[to]∗y∗p;$$dp[to]=pson[to]+y\ast p-pson[to]\ast y\ast p;$$ 别忘了卡精度…

题目链接：

Luogu 4284
BZOJ 3566

Ac 代码：

#include #include #include #include #include const int maxm=510000; const double eps=1e-8; int head[maxm],net[maxm<<1],to[maxm<<1],cnt; double p[maxm],dp[maxm],cost[maxm<<1],ans; int n; inline void addedge(int u,int v,double c) { cnt++; to[cnt]=v,cost[cnt]=c,net[cnt]=head[u],head[u]=cnt; } inline bool check(double a,double b) { return std::fabs(a-b)void dfs1(int now,int fa) { for(int i=head[now];i;i=net[i]) if(to[i]!=fa) { dfs1(to[i],now); p[now]=p[now]+p[to[i]]*cost[i]-p[now]*p[to[i]]*cost[i]; } } void dfs2(int now,int fa) { ans+=dp[now]; for(int i=head[now];i;i=net[i]) if(to[i]!=fa) { double P=cost[i]; double tmp=(1.0-p[to[i]]*P); if(check(tmp,0)) dp[to[i]]=1.0; else { double y=(dp[now]-p[to[i]]*P)/tmp; dp[to[i]]=p[to[i]]+y*P-p[to[i]]*y*P; } dfs2(to[i],now); } } int main() { scanf("%d",&n); for(int i=1;iint u,v; double c; scanf("%d%d%lf",&u,&v,&c); addedge(u,v,c/100),addedge(v,u,c/100); } for(int i=1;i<=n;i++) scanf("%lf",&p[i]),p[i]/=100; dfs1(1,0); dp[1]=p[1]; dfs2(1,0); printf("%.6lf ",ans); return 0; }