【LittleXi】题解 | #C旅游#

题意

从一个点出发，随机走，走过的点不能再走，问某点开始的最大期望步数

题解

简单地说就是，如果我们从0号点出发，可以很容易求出期望的步数，因为走到下一个点的概率是$1\mathrm{/}(du[i])1/(du[i])$
求完一个点之后，我们就可以考虑进行换根dp了，具体转移可以根据两个点的概率的求法，进行$O(1)O(1)$转移

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<int> vis;
vector<double> ans;
double dfs1(int root)
{
    vis[root] = 1;
    int sz = adj[root].size();
    double rep = 0;
    double p = 1.0 / (double)sz;
    if(root)
        p = 1.0 / (double)(sz-1);
    for (int i = 0; i < sz; i++)
    {
        int to = adj[root][i];
        if (vis[to])
            continue;
        double gp = dfs1(to)+1;
        rep += p * gp;
        qw[root][i] = gp;
    }
    return ans[root] = rep;
}

void dfs2(int root ,int fa)
{
    if (fa != -1)
    {
        double zp = ans[fa];
        int fsz = adj[fa].size();
        zp -= 1.0 / (double)fsz * (ans[root]+1);
        if(fsz>1)
            zp = (double)fsz / ((double)fsz-1) * zp;
        int sz = adj[root].size();
        zp = 1.0 / (double)sz * (1+zp);

        if(sz>1)
            zp += ((double)sz-1)/(double)sz*ans[root];
        ans[root] = zp;
    }
    vis[root] = 1;
    int sz = adj[root].size();
    for (int i = 0; i < sz; i++)
    {
        int to = adj[root][i];
        if (vis[to])
            continue;
        dfs2(to, root);
    }
}

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n, 0);
    adj.resize(n);
    qw.resize(n);
    ans.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        int x,y;
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    vis = v;
    ans[0] = dfs1(0);
    vis = v;
    dfs2(0, -1);
    double re = *max_element(ans.begin(), ans.end());
    printf("%.3lf", re);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
}