P16355 题解

I_will_AKIOI · 2026-04-26 14:52:29 · 题解

由树建出的图是基环森林。每个连通块点数和边数是一致的，因此每个连通块都恰好有一个环，最终连通块的个数就等于环的个数。

同时我们发现要构成一个环，肯定是在 dfs 树上由一条返祖边构成，也就是祖先不断连向儿子，儿子最后连到祖先上面。

设 E_x 为 x 成为环上最深的点的期望。由期望线性性可知，整张图环个数的期望就是 \displaystyle\sum_{i=1}^n E_i。乘上方案数就是答案。

如何计算期望呢？设 f_x 表示 x 能连到的边的数量，也就是 x 深度加上孩子数。一条路径构成环的概率就是路径上所有点 \frac{1}{f_x} 之积。因此有递推式，\displaystyle E_x=(E_{fa}+\frac{1}{f_{fa}})f_x。其中 fa 是 x 的父亲。

最后乘上方案数，答案就是 \displaystyle\Big(\prod_{i=1}^n f_i\Big) \Big(\sum_{i=1}^n E_i\Big)。

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define N 500005
using namespace std;
int n,ans=1,sum,dep[N],f[N],g[N];
vector<int>v[N];
int Pow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
void dfs(int k,int fa)
{
    g[k]=dep[k]+v[k].size()-(k!=1);
    f[k]=(f[fa]+Pow(g[fa],mod-2))*Pow(g[k],mod-2)%mod;
    for(int now:v[k]) if(now!=fa) dep[now]=dep[k]+1,dfs(now,k);
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) sum=(sum+f[i])%mod,ans=ans*g[i]%mod;
    cout<<ans*sum%mod;
    return 0;
}