题解：P16355 「Diligent-OI R3 C」彼方へ、名もなき海辺より

· · 题解

下文提到的 cnt_i 表示节点 i 有几种选择方案（其祖先个数加上儿子个数）。

我们来思考一下什么情况下会产生 1 的连通块个数贡献。

对于一个节点 i，以及其父亲 j。一开始我以为只要 j 不指向 i，并且 i 没有往前指（指向儿子），那这样 i 和 j 之间就断开了，连通块个数加一。但是这样是错误的，假如 i 的儿子又指向 j，那不就又连回去了？正确的结果是，i 的儿子选择继续指向儿子，直到有其中一儿子指向 i 为止，这样就能保证 i 单独出一个连通块。简单点说，就是出现了一个有向环。

好的，题目转化成了每一个点出度都为 1 的一张特殊图的所有可能下的有向环的个数总数是多少。显然是计数 dp。我们将 dp_i 设为以 i 为环的最底部出现的有向环总期望是多少。我们考虑其从其父亲 j 来转移。具体地，我们发现 dp_j 已经保证了上面出现有向环，我们要算让 i 加入这个有向环的期望。我们要改变 j 往前指，改成让其指向 i，这个期望是不变的，因为在有向环情况下， j 往前指只有一种可能（刚刚好形成由某节点开头的有向环）。然后我们现在要保证 i 要往前指，期望是 \frac{1}{cnt_i}，然后我们还要额外加上 i 和 j 自成一个小环的期望，即为 \frac{1}{cnt_i}\times\frac{1}{cnt_j}。

然后转移公式就推出来了：

dp_i=\frac{1}{cnt_i}\times(\frac{1}{cnt_j}+dp_j)

然后将 dp 累加起来得到总的期望，乘上总的可能数就可以了。

总可能数计算方式：S=\prod_{i=1}^ncnt_i。 :::success[code]


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353,N=5e5+5;
int n,sum=1,ans,u,v,cnt[N],dp[N];
vector<int> edge[N];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void dfs(int now,int fa,int k){
    (sum*=(k+edge[now].size()-(fa>0)))%=mod;
    cnt[now]=k+edge[now].size()-(fa>0);
    for(auto to:edge[now]) if(to!=fa) dfs(to,now,k+1);
}
void dfss(int now,int fa){
    if(fa) dp[now]=qpow(cnt[now],mod-2)%mod*(qpow(cnt[fa],mod-2)+dp[fa])%mod;
    for(auto to:edge[now]) if(to!=fa) dfss(to,now);
}
signed main(){
    cin>>n;
    for(int i = 1;i<n;i++)
        cin>>u>>v,
        edge[u].push_back(v),
        edge[v].push_back(u);
    dfs(1,0,0);
    dfss(1,0);
    for(int i = 1;i<=n;i++) (ans+=dp[i])%=mod;
    cout<<ans*sum%mod;
    return 0;
}