\(Description:\)
一棵树, 每个点 q[i] 的概率直接充电, 每条边 p[i] 的概率导电, 电可以沿边传递使其他点间接充电. 求进入充电状态的点期望个数.
- \(Sample\) \(Iuput:\)
- 3
- 1 2 50
- 1 3 50
- 50 0 0
- \(Sample\) \(Input:\)
- 5
- 1 2 90
- 1 3 80
- 1 4 70
- 1 5 60
- 100 10 20 30 40
- \(Solution:\)
考虑树形 dp, 首先我们需要明白, 其实我们要求的期望就是概率之和, 那么我们只要求出每个点的概率, 那么怎么求每个点的概率捏?
yzc 提供了一种神奇的办法, 考虑对于每个点, 先求出每个点的子树的概率和 \(f[u]\)
那么对于一个点 \(u\), 就只要让 \(u\) 的所有儿子到他的概率取个并集,
概率并的求法:
\(P(A \cup B)=P(A)+P(B)-P(A)*P(B)\)
第一遍 \(dfs\) 求出所有的 \(f\), 但这样只是求出了当前这个点的子树给他充电的概率, 还没有求父亲给他充电的概率.
那么再纪录一个 \(g\), 数组记录当前的总概率, 然后考虑 \(g\) 的转移:
那么我们考虑已经求出了他父亲的 \(g[fa]\) 要求 \(g[v]\)
那么就只要把 当前的点的子树对 \(g[fa]\) 的贡献给除掉就可以了.
求概率补集:
\(P(A)=\frac{P(A \cup B)-P(B)}{1-P(B)}\)\((注意特判 1-P(B)==0)\)
那么就可以愉快的用两次 \(dfs\) 求出答案.
- #include<bits/stdc++.h>
- using namespace std;
- typedef double DD;
- int n,En;
- DD ans;
- const int N=5e5+5;
- inline DD unit(DD a,DD b){
- return a+b-a*b;
- }
- inline DD split(DD a,DD b){
- if(fabs(1.0-b)==0) return 0;
- return (a-b)/(1.0-b);
- }
- DD f[N],g[N],p[N];
- int head[N];
- struct edge{
- int next,to;
- DD dis;
- }E[N<<1];
- inline void add(int from,int to,DD dis){
- E[++En].next=head[from];
- E[En].to=to;
- E[En].dis=dis;
- head[from]=En;
- }
- inline void dfs1(int u,int fa){
- f[u]=p[u];
- for(int i=head[u];i;i=E[i].next){
- int v=E[i].to;
- if(v==fa) continue;
- dfs1(v,u);
- f[u]=unit(f[u],f[v]*E[i].dis);
- }
- }
- inline void dfs2(int u,int fa){
- for(int i=head[u];i;i=E[i].next){
- int v=E[i].to;
- if(v==fa) continue;
- g[v]=unit(f[v],split(g[u],f[v]*E[i].dis)*E[i].dis);
- dfs2(v,u);
- }
- }
- int main(){
- scanf("%d",&n);
- for(int i=1;i<=n-1;++i){
- int u=0,v=0,w=0;
- scanf("%d%d%d",&u,&v,&w);
- add(u,v,(DD)w/100);
- add(v,u,(DD)w/100);
- }
- for(int i=1;i<=n;++i){
- int x=0;
- scanf("%d",&x);
- p[i]=(DD)x/100;
- }
- dfs1(1,1);
- g[1]=f[1];
- dfs2(1,1);
- for(int i=1;i<=n;++i) ans+=g[i];
- printf("%.6lf\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3025186.html