题意澄清
对于 dfs 遍历时，在某一个点进入子树的顺序并不是按输入顺序，而是假定随机选择未进入过的子树 (这纠结了我好久) 。
破题思路
首先可以明确这题不能推一个 \(O(1)\) 的式子来计算期望 (树的结构是随机的，对于所有点不存在均摊期望的可能) ，但是对于某一刻子树以根节点为起点时，一定是存在一个快速计算期望的式子 (不可能枚举起点还要枚举终点吧) 。
其次，考虑到需要对于每一个点作起点求出期望步数，又是一棵树，故树形 \(dp\) 肯定是必要的，同时还需要换根。
那么算法分析完了(树形 \(dp\) \(+\) 推以子树根作起点的步数期望式子)，就要具体实现算法了。
以子树根作起点的期望步数
对于每一棵子树，假设其根为 \(rt\) ，终点在其儿子 \(v\) 的子树中，如果下一步并未走向 \(v\) ，而是走向 \(u\) ，则需要花 \(2\times siz[u]\) ( \(siz[u]\) 为 \(u\) 子树内节点个数1) 步走回 \(rt\) ，那么对于在 \(v\) 之前走向 \(u\) 的概率相当于对于 \(rt\) 所有儿子的排列中 \(v\) 在 \(u\) 之后的概率，明显是 \(\frac{1}{2}\) ，故 \(u\) 子树对于步数的贡献即为 \(2\times siz[u]\times\frac{1}{2}=siz[u]\) ，所以对于以 \(rt\) 为根且以 \(rt\) 为起点的子树，其期望步数为
\[g_{rt} \gets \sum\limits_{u\in son_{rt}} ((siz_{rt}-siz_u)\times sum\_p_u+g_u) \]其中 \(g_u\) 为在 \(u\) 的子树中以 \(u\) 为根且以 \(u\) 为起点的期望步数，\(sum\_p_u\) 为以 \(u\) 的子树中的结点为终点的概率。
树形dp
对于第一次树形 \(dp\) 的式子我们已经在上一个部分推出来了，难点在于换根时的式子。我经常使用的方法是不去思考意义，只思考原式的 “逆式” 。
先明确一下定义。
\[\begin{aligned} & \text{依据}\ u\ \text{去更新儿子}\ v\\ & g,siz,sum\_p \text{意义同上}\\ & f_u:\text{以}\ u\ \text{为起点的期望步数}\\ & p2_u:\text{以}\ u\ \text{为终点的概率}\\ & except\_v:\text{对于}\ v\ \text{的父亲}\ u\ \text{没有子树}\ v\ \text{时}\ g_u\ \text{的值} \end{aligned} \]首先我们先处理式子中的 \(g_u\) ，即 \(except\_v\) ，既然是消去影响，故是用 \(f_u\) 去减去影响。
- 终点不在 \(v\) 的子树中
概率为 \(1-sum\_p_v-p2_u\)
贡献为 \(siz_v\)
影响为 \((1-sum\_p_v-p2_u)\times(siz_v)\) - 终点在 \(v\) 的子树中
概率为 \(sum\_p_v\)
贡献为 \(n-siz_v\)
影响为 \(sum\_p_v\times(n-siz_v)\)
故
\[except\_v \gets f_u - siz_v \times (1 - p2_u - sum\_p_v) - (n - siz_v) \times sum\_p_v \]接下来我们处理以 \(v\) 为起点的期望步数。
- 终点在原本 \(v\) 的子树中
概率为 \(sum\_p_v-p2_v\)
贡献为 \(n-siz_v\)
期望步数为 \((sum\_p_v-p2_v)\times(b-siz_v)\) - 终点不在原本 \(v\) 的子树中
模仿原 \(dp\) 式子可得 \((n-(n-siz_v))\times(1-sum\_p_v)+except\_v\)
故
\[f_v \gets (n - siz_v) \times (sum\_p_v - p2_v) + (n - (n - siz_v)) \times (1 - sum\_p_v) + except\_v \]实现
综合上述内容，便有了以下代码。
/*
address:https://codeforces.com/problemset/problem/123/E
AC 2024/8/28 12:26
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int>G[N];
int n;
double p1[N], p2[N];
int sum1, sum2;
double f[N], g[N], sum_p[N];
int siz[N];
inline void dfs1(int u, int fa) {
sum_p[u] = p2[u];
siz[u] = 1;
for (auto v : G[u]) {
if (v == fa) continue;
dfs1(v, u);
sum_p[u] += sum_p[v];
siz[u] += siz[v];
}
for (auto v : G[u]) {
if (v == fa) continue;
g[u] += (siz[u] - siz[v]) * sum_p[v] + g[v];
}
}
inline void dfs2(int u, int fa) {
for (auto v : G[u]) {
if (v == fa) continue;
double except_v = f[u] - siz[v] * (1 - p2[u] - sum_p[v]) - (n - siz[v]) * sum_p[v];
f[v] = (n - siz[v]) * (sum_p[v] - p2[v]) + (n - (n - siz[v])) * (1 - sum_p[v]) + except_v;
dfs2(v, u);
}
}
int main() {
scanf("%d", &n);
for (int i = 1;i < n;i++) {
int u, v;scanf("%d%d", &u, &v);
G[u].push_back(v);G[v].push_back(u);
}
for (int i = 1;i <= n;i++) scanf("%lf%lf", &p1[i], &p2[i]), sum1 += p1[i], sum2 += p2[i];
for (int i = 1;i <= n;i++) p1[i] /= sum1, p2[i] /= sum2;
dfs1(1, 0);
f[1] = g[1];
dfs2(1, 0);
double ans = 0;
for (int i = 1;i <= n;i++) ans += p1[i] * f[i];
printf("%.12lf", ans);
return 0;
}
The end
一道概率期望加树形 \(dp\) 的好题，具备一定思维难度，但又可以一步步推出式子，对于学未至极但又学习良多的我是不多的提升较大的练习。
标签：p2,int,text,sum,CF,times,123E,siz,Maze From： https://www.cnblogs.com/keysky/p/18678632