ARC165E Random Isolation 题解

Coffee_zzz · 2025-10-12 18:39:19 · 题解

由于每个点最多只会被删除一次，且每个连通块不会增大，所以可以将题意转化为：随机一个排列 p，从 1 到 n 依次考虑每个点 p_i，如果点 p_i 所处的连通块大小大于 k 则删除点 p_i，否则不进行操作，求期望删除次数。

设 P(G) 表示原树的子图 G 作为一个完整的连通块的出现概率。如果图 G 包含大于 k 个点，那么当图 G 作为一个完整的连通块出现时，一定会进行恰好一次删除操作。所以，期望删除次数就等于每个包含大于 k 个点的子图 G 作为一个完整的连通块的出现概率之和，即 \sum\limits_{|G|>k} P(G)。

接下来考虑怎么计算 P(G)。设图 G 包含 a 个点，原树中有 b 个点与图 G 中的点相连，那么要求只有这 b 个点在排列中的顺序均在这 a 个点前，所以 P(G) 等于 \dfrac{a!b!}{(a+b)!}。

于是可以进行树形 dp：设 f_{u,i,j} 表示，满足图 G 中深度最小的点为 u，包含 i 个点，以 u 为根的子树中有 j 个点与图 G 中的点相连的原树的子图 G 的数量。直接从儿子处转移即可。

时间复杂度 \mathcal O(n^4)。

const int N=105,mod=998244353;
int n,k,siz[N],fac[N],infac[N],f[N][N][N],g[N][N],ans;
vector <int> ve[N];
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        b>>=1;
        a=1ll*a*a%mod;
    }
    return res;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
void dfs(int u,int fa){
    f[u][1][0]=1,siz[u]=1;
    for(auto v:ve[u]){
        if(v==fa) continue;
        dfs(v,u);
        memset(g,0,sizeof g);
        for(int i=0;i<=siz[u];i++) for(int j=0;i+j<=siz[u];j++) for(int p=0;p<=siz[v];p++) for(int q=0;p+q<=siz[v];q++) add(g[i+p][j+q],1ll*f[u][i][j]*f[v][p][q]%mod); 
        siz[u]+=siz[v];
        for(int i=0;i<=siz[u];i++) for(int j=0;j<=siz[u];j++) f[u][i][j]=g[i][j];
    }
    f[u][0][1]=1;
}
void solve(){
    cin>>n>>k;
    for(int i=1,u,v;i<n;i++) cin>>u>>v,ve[u].pb(v),ve[v].pb(u);
    fac[0]=infac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    infac[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
    dfs(1,0);
    for(int u=1;u<=n;u++){
        for(int i=k+1;i<=siz[u];i++){
            for(int j=0;i+j<=siz[u];j++){
                int p=j+(u!=1);
                add(ans,1ll*f[u][i][j]*fac[i]%mod*fac[p]%mod*infac[i+p]%mod);
            }
        }
    }
    cout<<ans<<endl;
}