洛谷P3412 仓鼠找$Sugar\ II$题解(期望+统计论？)

时间：2023-03-09 09:04:05
洛谷P3412 仓鼠找$Sugar\ II$题解(期望+统计论？)

洛谷P3412 仓鼠找\(Sugar\ II\)题解(期望+统计论？)

标签：题解

阅读体验：https://zybuluo.com/Junlier/note/1327573

原题链接：洛谷P3412 仓鼠找sugar II

好像只有洛谷有诶。。。

日常吐槽

这个期望题开发新思维方式还是比较好的。。。

毕竟还是很难想的。。。鸣谢\(fdfDarkfire\)教我做这个题！

题解来了

很容易发现答案就是\(\dfrac{\sum_{i=1}^{n}\sum_{i=1}^{n}dis[i][j]}{n^2}\% MOD\)是吧

但是不会在短时间内算分子部分啊。。。

但是我们可以发现：如果可以固定住终点，那么会很容易算

所以我们先钦定终点在\(1\)，然后考虑某种方法来启发计算所有点为终点的情况

终点在\(1\)

不妨把\(1\)作为根

本来一个\(DFS\)可以搞定，但是对正解毫无启发，所以再想一下

我们设\(f[now]\)表示从\(now\)跳到\(fa[now]\)的期望步数

那么有(这个自己思考一下就行了)（\(qw\)是儿子，\(d\)是度数）$$f[now]=1+\frac{1}{d[now]}×\sum(f[qw]+f[now])$$草稿纸上化简一下会得到\(f[now]=d[now]+\sum f[qw]\)

哇，这不是很美丽！得到\(f[now]=\sum d[x]\)（\(x\)在\(now\)的子树内）

突然发现\(f\)数组只和子树度数和有关，嘿嘿、、、

这样也可以很方便地统计答案是吧：\(Ans=siz[now]×f[now]\)

说一下为什么，\(now\)往\(fa[now]\)的边只会被\(now\)的子树中节点去用\(f[x]\)走是吧，而\(f[now]\)全统计到了\(f[x]\)，所以直接乘

那么我们发现，固定一个点为终点时答案只和当前点为根时的$\sum $子树大小×子树度数和 有关

拓展到终点随机

上面那个结论很重要

我们现在对每个点进行考虑，是不是它有很多个方向出去，那些方向都有可能有终点

我们分别计算那些终点是在哪一个方向

  1. 肯定还是先以\(1\)为根把上面所需的所有东西处理出来
  2. 枚举每个点枚举边考虑根的方向
  3. 如果根在树中的\(1\)的方向，就是\(fa[now]\)方向，肯定有\(Ans+=siz[now]*f[now]*(n-siz[now])%MOD\)

    意思是对于根在\(fa[now]\)方向有\((n-siz[now])\)种位置，而每种位置此时贡献都是\(siz[now]*f[now]\)（上面说了的）
  4. 如果根在树中的某个儿子方向，就是\(qw\)方向，肯定有\((n-siz[qw])*(tot-f[qw])*siz[qw])\)，含义的话根据\(fa[now]\)方向的情况自己想一下吧

PS：上面这一段有不理解可以根据代码看

这样我们就统计完了总表达式的分子部分，乘个逆元就解决了。。。

#include<bits/stdc++.h>

#define il inline

#define rg register

#define ldb double

#define lst long long

#define rgt register int

#define N 100050

#define qw ljl[i].to

#define MOD 998244353

using namespace std;

const int Inf=1e9;

il int MAX(rgt x,rgt y){return x>y?x:y;}

il int MIN(rgt x,rgt y){return x<y?x:y;}

il int read()

{

    int s=0,m=0;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}

    while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();

    return m?-s:s;

}

int n;lst Ans;

int hd[N],cnt,tot;

int f[N],siz[N],fa[N],d[N];

//f: the step's expectation of now jumps to fa[now] (as the root of 1)

//f[now]=Σf[qw]+d[now]=totd[](in son_tree)     写题的时候写的傻逼英语。。。

struct EDGE{int to,nxt;}ljl[N<<1];

il void Add(rgt p,rgt q){ljl[++cnt]=(EDGE){q,hd[p]},hd[p]=cnt;}

il void ADD(rg lst &x,rg lst y){x+=y;if(x>MOD)x-=MOD;}

il int qpow(rg lst x,rgt y)

{

    rg lst ret=1;

    while(y)

    {

        if(y&1)ret=(ret*x)%MOD;

        x=(x*x)%MOD,y>>=1;

    }return ret;

}

void Dfs(rgt now,rgt fm)

{

    fa[now]=fm,siz[now]=1,f[now]=d[now];

    for(rgt i=hd[now];i;i=ljl[i].nxt)

    {

        if(qw==fm)continue;Dfs(qw,now);

        siz[now]+=siz[qw],f[now]+=f[qw];

    }

}

int main()

{

    n=read();

    for(rgt i=1,p,q;i<n;++i)

    {

        p=read(),q=read();

        ++d[p],++d[q],Add(p,q),Add(q,p);

    }Dfs(1,0);

    for(rgt i=1;i<=n;++i)tot+=d[i];

    for(rgt now=1;now<=n;++now)

        for(rgt i=hd[now];i;i=ljl[i].nxt)

        {

            if(qw==fa[now])ADD(Ans,1LL*siz[now]*f[now]%MOD*(n-siz[now])%MOD);

            else ADD(Ans,1LL*(n-siz[qw])*(tot-f[qw])%MOD*siz[qw]%MOD);

        }

    return printf("%lld\n",Ans*qpow(1LL*n*n%MOD,MOD-2)%MOD),0;

}