• 前言
• 题目大意
• 思路
• 代码
• 总结

前言

话说CF比赛难度跨越好大，A题是红B直接上蓝了😅

题目大意

给出一颗树，$n$ 个结点。求走一条路到叶子结点到 $1$ 边的个数的平均期望。
$1\leq n\leq 10^5$

思路

首先遍历dfs是可以想到的。我一开始想成了直接走到叶子结点记录完之后求一下平均值。这是错的。首先，由于本题是有不同的路径的，所以每一次的走都会影响最终结果。上面的做法可以理解为直接在叶子层选，不考虑路径不同所带来的影响。

正解是树上dp。可以知道，我们从一个结点选择一个子结点时每一个子结点可能被走到的概率都是 $\frac{1}{son}$，也就是孩子个数分之一的可能性，很好理解。那么，假如我是倒数第二层结点的其中一个，我的期望是多少？是不是 $\frac{\Sigma_{1}^{son}1}{son}$，因为只有一条边连接，并且上面说了有 $\frac{1}{son}$ 的概率选择一个，也就是求平均值。之后再把这个当成最后一层然后再重复，这样就可以看出来是dp了。总结一下公式吧。

$\frac{\Sigma_{1}^{son} dp[v]}{son}$

子结点的期望之和再求一个平均值得出当前的期望。注意要提前先dfs再做公式。

代码

#include <cstdio>

using namespace std;
typedef long long ll;
const ll MAXN = 1e6 + 5;
struct edge {
    ll to, nxt;
} e[MAXN];
ll head[MAXN], tot;

void add(ll u, ll v) {
    e[++tot].nxt = head[u];
    e[tot].to = v;
    head[u] = tot;
}

double dp[MAXN];

void dfs(ll u, ll f) {
    ll son_num = 0;
    for (ll i = head[u]; i; i = e[i].nxt) {
        if (e[i].to == f) {
            continue;
        }
        dfs(e[i].to, u);
        dp[u] += dp[e[i].to] + 1;
        son_num++;
    }
    if (son_num) {
        dp[u] /= son_num;
    }
}

ll n;

int main() {
    scanf("%lld", &n);
    for (int i = 1; i < n; ++i) {
        ll u, V;
        scanf("%lld%lld", &u, &V);
        add(u, V);
        add(V, u);
    }
    dfs(1, 1);
    printf("%0.10lf\n", dp[1]);
    return 0;
}

总结

本题让我们加深了对期望的理解，排除了一开始错误的做法并分析了错误原因。