【[SHOI2014]概率充电器】解题报告
partychicken
2018-12-31 16:43:11
## 概率+树型dp
### Part I
拿到这道题的一瞬间，反应了一下——**这不是道假期望题吗？**
为什么？我们考虑这道题的答案
$$\sum p_i*w_i$$
而，$w_i$全TMD是$1$ ！！！所以，就对$p_i$**求个和**就行了。
**所以这题是概率dp**
___
### Part II
考虑这个dp怎么写,一片乌鸦飞过，这TM怎么写啊！！！
聪明的同学不难发现，我们任意选取一个点作为根，然后考虑每个节点，不仅它的子节点可以对它亮的概率产生贡献，它的**父节点同样可以产生贡献**。
这咋dp啊？这dp个p啊？
诶？好像有个做法：我们枚举每个儿子为根，然后对每种情况进行处理，每次根节点的答案是正确的，因为它没有父亲~~（没爹的孩子果然简单易懂呢）~~。复杂度$O(n^2)$,看一眼数据范围，50w，emmm，~~松松松n方过百万~~显然过不去
考虑优化，发现每次换根的贡献只有一部分点，我们把这些点维护一下，复杂度。。。等等，这咋写啊？然后，我的思路就离正解越来越远。。。~~思路逐渐变态~~
___
### Part III
上回书说到，每个点的概率来源有三
- 它的子节点对它的贡献（即整棵子树中有节点进入充电状态，且通过边传递给它的概率）
- 它自己的贡献（即它最初为充电状态的概率）
- 它的父节点对它的贡献（即除子树外的部分有节点进入充电状态，且通过边传递给它的概率）
如果只考虑前两个，貌似dp方程比较显然
$$dp[now]+=(1-dp[now])\times dp[v]\times e[i].val$$
其中，$dp[x]$指点$x$的概率，$v$是$now$的子节点，$e[i].val$是连接$now$,$v$的边连通的概率
然后，考虑父节点的贡献。我们用上面dp转移出的概率从根节点向下转移，这样**每个节点向下转移的时候已经是被充分计算过的**，没有后效性。
感觉哪里不对。。。
以一对儿父子关系为例，$a$是$b$的父节点。第一遍dp的时候，**$b$对$a$产生了贡献**，第二遍dp时**这个贡献又作为$a$的一部分贡献给了$b$**。
发现统计重复了，我们需要的是**$b$对$a$作贡献前$a$的dp值**，换言之，即**把$b$对$a$做的贡献排除出去**。
考虑第一遍的dp方程
$$dp[a]_{now}=dp[a]_{last}+(1-dp[a]_{last})\times dp[b]\times e[i].val$$
每个变量的意义上同，特殊地，我们区分了$dp[a]_{now}$与$dp[a]_{last}$，分别指**转移后的dp[a] (即现在已知的dp[a])** 与 **转移前的dp[a] (即所求的,对dp[b] 在第二次dp中产生贡献的部分）**
化简可得
$$dp[a]_{last}=\dfrac{dp[a]_{now}-dp[b]\times e[i].val}{1-dp[b]\times e[i].val}$$
求得$dp_{last}$后，沿用第一次的转移
$$dp[b]+=(1-dp[b])\times dp[a]_{last}\times e[i].val$$
进行第二次dp，所得的结果就是最终答案。此题完结。
另外还有一些细节见代码（当然，看完上面的那些要是自己能打出来就不要看代码了）
___
### Part IV
又到了喜闻乐见的放代码环节
```
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7;
struct Edge
{
int to,nxt;
double val;
Edge(){}
Edge(int to,int nxt,double val):to(to),nxt(nxt),val(val){}
}e[1000010];
int head[500010],cnt;
void addedge(int u,int v,double val)
{
e[++cnt]=Edge(v,head[u],val);
head[u]=cnt;
}
int n;
double dp[500010];
void dfs1(int now,int fa)//第一遍dp
{
for(int i=head[now];i;i=e[i].nxt)
{
int vs=e[i].to;
if(fa==vs) continue;
dfs1(vs,now);
dp[now]+=dp[vs]*(1-dp[now])*e[i].val;
}
}
void dfs2(int now,int fa)//第二遍dp
{
for(int i=head[now];i;i=e[i].nxt)
{
int vs=e[i].to;
if(fa==vs) continue;
if(fabs(1-dp[vs]*e[i].val)<=eps)
//坑：如果分母为0直接跳过。
//原因：分母为0说明dp[vs]为1，不需要贡献
{
dfs2(vs,now);
continue;
}
dp[vs]+=(1-dp[vs])*(dp[now]-dp[vs]*e[i].val)/(1-dp[vs]*e[i].val)*e[i].val;
dfs2(vs,now);
}
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
double val;
cin>>u>>v>>val;
addedge(u,v,val/100);
addedge(v,u,val/100);
}
for(int i=1;i<=n;i++)
{
cin>>dp[i];//自己的贡献一开始就算进去
dp[i]/=100;
}
dfs1(1,0);
dfs2(1,0);
double ans=0;
for(int i=1;i<=n;i++)
{
ans+=dp[i];
}
cout<<fixed<<setprecision(6);//保留6位小数
cout<<ans<<endl;
}
```
___
### Part V
回过头来看这道题，发现我一开始的思路并没有问题，只是没想清楚。
我们统计父节点贡献的时候，**本质上就是换根,**把原来的父节点变成子节点，那么**原来对父节点的贡献要还原，而父节点要对子节点进行贡献**。而第二遍dp的本质是对重复信息的利用，以达到换根效率的最优效果——$O(1)$换根。
题目不错，值得一做。