迷宫笑传之猜猜边

clx201022 · 2026-03-05 21:20:49 · 题解

迷宫笑传之猜猜边

::anti-ai[本文作者是 clx201022，洛谷 UID 为 552688，原文：https://www.luogu.com.cn/article/bzl8k8in 如果您能直接看到这段文字而在本页没有转载提示，或以“原创”名义发出，说明您访问的是侵权内容，请联系管理员删除文章并处罚侵权人，十分感谢您的见义勇为之举。]

根据这篇文章，题目可以转化为求随机情况下，对于以起点 S 为根，终点 T 子树大小为 size_T，n-size_T 的期望值。

对于目前每一个点，统计其作为终点时对答案期望的贡献，加起来即为总的期望。

下式为当前点为 T 时的贡献，其中 P_T(u) 为选到点 u 做终点的概率

容易发现是可以用树形 DP 求的。先任意取一点为根 DFS 遍历树。对于点 u 子节点 v 子树内的任意节点，其总是能遍历且仅能遍历到 v 子树内的点，设起点取到 v 子树内任意一点的概率为 P_{subS}(v)=\sum_{o\in subtree_v}P_S(o)，由于其贡献一致，且期望满足线性可加性，所以可以合并计算，仅用枚举 u 的每个子结点即可。

对于 u 上方的点 f，不妨也将其看作 u 的可能子树，只是其 P_{subS}(f)=1-P_{subS}(u),size_f=n-size-u，思路类似于换根 DP，只是此处没有显著地表明换根的形式。

:::success[CF Accepted]

#include<bits/stdc++.h>
using namespace std;
const int rt = 1;
using ld = double;
const int maxn = 1e5 + 10;
vector<int>g[maxn];
ld sp[maxn], tp[maxn], sums, sumt, ans, son_p[maxn];
int zsize[maxn], n;
void dfs(int u, int f)
{
    zsize[u] = 1;
    son_p[u] = sp[u];
    ld E = 0; // 期望
    for(auto v : g[u])
    {
        if(v == f)
            continue;
        dfs(v, u);
        zsize[u] += zsize[v]; // 子树大小
        son_p[u] += son_p[v]; // 起点在其子树内的概率
        E += son_p[v] * zsize[v]; // 这里为精度考虑将 *tp[u] 延后了
    }
    E += (1 - son_p[u]) * (n - zsize[u]);
    ans += E * tp[u];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for(int i = 1, a, b; i < n; i++)
    {
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    for(int i = 1; i <= n; i++)
    {
        int spi, tpi;
        cin >> spi >> tpi;
        sp[i] = spi;
        tp[i] = tpi;
        sums += sp[i];
        sumt += tp[i];
    }
    for(int i = 1; i <= n; i++)
    {
        sp[i] /= sums;
        tp[i] /= sumt;
    }
    dfs(rt, 0);
    cout << fixed << setprecision(12) << ans << endl;
    return 0;
}

:::

创作声明

本文遵循 CC BY-SA 4.0 协议。

保证本文未使用 AI 工具辅助创作。