小仓鼠的和他的基(mei)友(zi)sugar住在地下洞穴中,每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室(a,是任意的)他的基友卧室(b,还是任意的)。(注意,a有可能等于b。)然而小仓鼠学OI学傻了,不知道怎么怎么样才能最短的走到目的地。于是他只能随便乱走。当他在每一个节点时,等概率到这个点的母亲或者所有孩子节点(例如这个节点有一个母亲节点和两个子节点,那么下一步走到这3个节点的概率都是1/3)。一但走到了他基友的卧室,就会停下。

现在小仓鼠希望知道,他走到目的地时,走的步数的期望。这个期望本来是一个有理数,但是为了避免误差,我们要求对这个有理数取模,%998244353。

链接 🔗

「P3412」 仓鼠找sugar II

题解 ❓

by Created_equal1
首先dp出每个点到其父亲的期望游走距离和每个点父亲到这个点的期望游走距离(可以自己推式子,可以直接拉经典结论),这样我们就相当于把一个双向边拆成两条单向边。然后考虑如何统计答案。
考虑统计每条边对答案的贡献。枚举某条边E,其对答案产生的贡献就是在E一边的点数E在另一边的点数(E正着走的期望距离+E倒着走的期望距离)

代码

const int mod = 998244353;
const double eps = 1e-8;
const int N = 2e5+10;
V G[N];
ll sum,fa[N],sz[N],d[N];
void dfs(ll x,ll f)
{
    d[x] = G[x].size();
    sz[x] = 1; fa[x] = f;
    for(auto v: G[x])
    {
        if(v == f) continue;
        dfs(v,x); sz[x] += sz[v];
        d[x] += d[v];
    }
}
int main()
{
//    __IN;__OUT;
    ll n;RLL(n);
    FOR(i,1,n-1)
    {
        ll x,y;
        RLL2(x,y);
        G[x].pb(y);G[y].pb(x);
    }
    FOR(i,1,n) sum += G[i].size();
    dfs(1,0);
    ll ans = 0;
    FOR(x,1,n)
    {
        for(auto v:G[x])
        {
            if(v==fa[x]) ans=(ans+1ll*d[x]*sz[x]%mod*(n-sz[x])%mod)%mod;
            else ans=(ans+1ll*(sum-d[v])*(n-sz[v])%mod*sz[v]%mod)%mod;
        }
    }
    PLN(ans * fpow(n*n % mod,mod-2,mod) % mod);
    return 0;
}