题意:

给出一棵n个节点的树,我们每次随机染黑一个叶子节点(可以重复染黑),操作无限次后,这棵树的所有叶子节点必然全部会被染成黑色。定义R为这棵树不经过黑点的直径,求使R第一次变小期望的步数。

分析:

我们思考,我们思考,我们肯定要求出所有叶子节点,然后我们叫他tot,然后我们思考,如何让一条直径变短,那么假设我们求出了所有直径的端点…..对于直径长度为奇数,那么所有直径都经过一条边,边左右两棵子树中的端点构成两个集合,然后这两个集合中各选一个点连成的边构成了一条直径,当直径变短的情况下就是其中一个集合全被染黑了……我们考虑直径是偶数的情况,这样所有的直径过一个点,这个点把树拆成好多小子树,然后其中的直径端点就构成了很多集合,同理,这时直径减小的情况就是只剩下一个集合的情况…..
然后我们怎么求期望补数呢…..首先来说一个结论,假设一共有N个点,已经染黑了i个,然后我们随机染,多染黑一个的期望步数就是\frac{N}{N-i}….
所以我们现在开始求期望了,假设一共有num个元素(端点),tot个叶子节点.我们枚举最终剩下的集合为i,其中有siz_i个元素,然后这其中有j个元素被染黑,然后我们要枚举所有情况,(为了保证计算不重复,我们要保证最后的一个元素,不是在最终集合中的…..),然后由于我们要求的是方案,所有,前面的我们还要排序….然后式子大概
\binom{siz_i}{j}\times (num-siz_i+j-1)!\times \sum_{siz_i-j+1\leq k\leq num}{\frac{tot}{k}}
然后我们发现我们还要乘上前面的最后一的点,以及后面那siz_i-j的点的全排列,最后除以num!….
\binom{siz_i}{j}\times (num-siz_i+j-1)!\times \sum_{siz_i-j+1\leq k\leq num}{\frac{tot}{k}}\times (num-siz_i) \times (siz_i-j)! \times \frac{1}{num!}
所以ans的总式子就是…
\sum_{0\leq j \leq siz_i}\bigg(\binom{siz_i}{j}\times (num-siz_i+j-1)!\times \sum_{siz_i-j+1\leq k\leq num}{\frac{tot}{k}}\times (num-siz_i) \times (siz_i-j)! \times \frac{1}{num!} \bigg)
然后我们预处理各种东西就好了……

代码:

#pragma GCC optimise(2)
#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL N=5e5+10;
const LL mod=998244353;
const double eps=1e-12;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,du[N];
int head[N],cnt;
struct Edge{int next,to;}edge[N*2];
void add(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
int Len,yuan;
int dfs1(int now,int fa,int dep)
{
    if(dep>Len) Len=dep,yuan=now;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs1(to,now,dep+1);
    }
}
int son[N];
int dfs2(int now,int fa)
{
    int ret=0;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        int tmp=dfs2(to,now)+1;
        if(ret<tmp)
            ret=tmp,son[now]=to;
    }
    return ret;
}
int tot,jihe[N],num;
void dfs_ji(int now,int fa,int dep)
{
    if(dep==0) jihe[tot]++,num++;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs_ji(to,now,dep-1);
    }
}
int fac[N],inv[N];
int my_pow(int a,int b,int ret=1)
{
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;b>>=1;
    }return ret;
}
int yjc[N],wzy[N],sb;
void init()
{
    fac[0]=fac[1]=inv[1]=1;
    for(int i=2;i<=N-10;i++) fac[i]=fac[i-1]*i%mod;
    for(int i=2;i<=N-10;i++) inv[i]=my_pow(i,mod-2);
    wzy[N-10]=my_pow(fac[N-10],mod-2);
    for (int i=N-11;i>=0;i--) wzy[i]=(i+1)*wzy[i+1]%mod;
    for(int i=num;i>=1;i--) yjc[i]=(yjc[i+1]+sb*inv[i]%mod)%mod;
}
int C(int a,int b){return fac[a]*wzy[a-b]%mod*wzy[b]%mod;}
signed main()
{
    read(n);
    for(int i=1,u,v;i<n;i++)
        read(u),read(v),add(u,v),add(v,u),du[u]++,du[v]++;
    for(int i=1;i<=n;i++) if(du[i]==1) sb++;
    dfs1(1,0,1);
    Len=dfs2(yuan,0);
    if(Len%2==1)
    {
        int now=yuan,L,R;
        for(int i=0;i<=Len;i++)
        {
            if(i==Len/2) L=now;
            if(i==Len/2+1) R=now;
            now=son[now];
        }
        ++tot;dfs_ji(L,R,Len/2);
        ++tot;dfs_ji(R,L,Len/2);
    }
    else
    {
        int now=yuan;
        for(int i=1;i<=Len/2;i++)
            now=son[now];
        for(int i=head[now];i;i=edge[i].next)
        {
            ++tot;dfs_ji(edge[i].to,now,Len/2-1);
            if(!jihe[tot]) tot--;
        }
    }
    init();
    int ans=0;
    for(int i=1;i<=tot;i++)//枚举集合....
    {
        int siz=jihe[i];
        for(int j=0;j<siz;j++) //枚举集合里的点
            (ans+=C(siz,j)*fac[num-siz+j-1]%mod*(num-siz)%mod*yjc[siz-j+1]%mod*fac[siz-j]%mod*wzy[num]%mod)%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注