- 概率DP是DP中一个非常重要且较难的DP类型。其题型灵活多变，尤其爱与树形DP结合，同时很可能需要各种数据结构优化。
- 其主要考点便是DP方程的建立与维护。由于“概率”二字，许多时候分类讨论与小数运算也是不可避免的。
因此，概率DP对选手的逻辑思维与代码能力也有很高的要求，可以说是DP中的集大成者。
P2081 [NOI2012] 迷失游乐园
- 题意：给定一颗有 \(n\) 个点的树或基环树，每条边有边权 \(w_i\)
求从每个点开始，在树上随机不重地走，最后的期望经过的边权和。
对于每个节点，其下一步走到其任意相邻点的概率是相同的。 - 数据范围 \(n\le 1e5,w_i \le 100\)
普通树
先考虑在普通的树上怎么做。假设我们先钦定 \(rt\) 为根节点，那么对于每个除根以外的节点，其第一步的走法有两种：
- 向父亲走
- 向儿子走
容易发现，如果我们已经求出这个点所有儿子再向下走的概率，那这个点向儿子走的概率转移是朴素的。
设第一步向下走的期望权值为 \(down_u\)，则有
- 其中 \(son_u\) 代表 \(u\) 的儿子个数，\(v\) 代表 \(u\) 的某一个儿子。
而向父亲走的情况稍微复杂了一点。由于这个点走向父亲后还能再向其其他儿子走，也可以继续向上，因此情况要考虑完全
设 \(u\) 第一步向上的期望权值 为 \(up_u\)，则有
- 其中 \(k\) 是 \(u\) 的父亲，\(fa_k\) 是 \(k\) 父亲的数量。这听起来可能有些奇怪，因为普通树只有一个或没有父亲。
不过在一会要讨论的基环树中，\(fa_u\) 就能体现出作用 - \(up_k\cdot fa_k\) 是继续向上走的贡献，\(down_k\cdot son_k\) 是 \(k\) 又向下走的贡献。
但因为不能重复走到 \(u\) 点，因此需要减去贡献。注意上面是总的贡献，因此可以直接减
最后，因为不能走回 \(u\)，因此总共有 \(son_k+fa_k-1\) 种情况。 - 由于 \(up_u\) 需要由 \(down_u\) 与 \(down_k\) 推出，因此对于普通树，先求 \(down\) 再求 \(up\) 即可。
但需要注意根节点没有父亲，因此处理 \(up\) 时，注意从根节点的所有儿子开始处理。
点击查看代码
void make_down(int u,int k)
{
for(int i=0;i<tot[u];i++)
{
int v=q[u][i].v;if(vis[v]||v==k) continue;
fa[v]=1;make_down(v,u);son[u]++;down[u]+=1.0*(down[v]+q[u][i].w);
}
if(son[u]) down[u]=down[u]/son[u];
}
void make_up(int u,int k,ld w)
{
up[u]=w;
if(fa[k]+son[k]-1)
up[u]=up[u]+(up[k]*fa[k]+down[k]*son[k]-down[u]-w)/(son[k]+fa[k]-1);
for(int i=0;i<tot[u];i++){
int v=q[u][i].v;if(v==k||vis[v]) continue;
make_up(v,u,q[u][i].w);
}
}
void work1()
{
make_down(1,0);
for(int i=0;i<tot[1];i++) make_up(q[1][i].v,1,q[1][i].w);
}
基环树
- 可以先画个图。
- 红边是环上的边。可以发现，如果我们将红边删掉，就是一片森林。因此对