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

· · 题解

先观察新图的性质。

每个结点都连出去一个边，所以新图是基环树森林。连通块数量即环的数量。

每条边都连接祖孙，所以每个环都是由一对祖孙的路径上所有结点组成。

再计算每个环的贡献。

每个环被确定，当且仅当环上所有结点的连边情况确定。设 cnt_u 表示结点 u 的祖先与儿子数量之和，则贡献为环外点的所有选法，即 \prod\limits_{u\text{不在环上}}cnt_u=\frac{\prod cnt_u}{\prod\limits_{u\text{在环上}}cnt_u}。

设二元组 (a,b) 表示点 a 到 b 形成的环，则答案为

\begin{aligned} {}&\sum_{a=2}^n\sum_{b\text{是}a{祖先}}\frac{\prod cnt_u}{\prod\limits_{u\text{在}(a,b){上}}cnt_u}\\ =&\prod cnt_u\sum_{a=2}^n\sum_{b\text{是}a{祖先}}\frac{1}{\prod\limits_{u\text{在}(a,b){上}}cnt_u} \end{aligned}

枚举 a，维护 sum=\sum\frac{1}{\prod\limits_{u\text{在}(a,b){上}}cnt_u} 即可。每次往下遍历就乘上 \frac{1}{cnt_u}，计算完答案后才加上 \frac{1}{cnt_u}（因为不可以自环）。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define mid ((l+r)>>1)
#define bmid ((l+r+1)>>1)
#define pb push_back
#define eb emplace_back
#define fswap(a,b) ((a)^=(b)^=(a)^=(b))
using namespace std;
using ll= long long;
#ifndef ONLINE_JUDGE
template <typename tp>
void _debug(const tp& t) {cerr<<t<<'\n';}
template <typename tp,typename... args>
void _debug(const tp& t, const args&... rest) {cerr<<t<<' ';_debug(rest...);}
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)
#else
#define debug(...) 0
#endif
const int N=500005,H=N<<2,inf=1000000000,mod=998244353;
vector<int> g[N];
int n,dep[N];
ll ans,tot=1,cnt[N];
void dfs1(int u,int p) {
    cnt[u]=dep[u];
    for(int& v: g[u]) if(v!=p) {
        dep[v]=dep[u]+1,cnt[u]++;
        dfs1(v,u);
    }
    tot=tot*cnt[u]%mod;
}
ll pw(ll x,ll y) {
    ll ret=1;
    for(x%=mod;y;y>>=1,x=x*x%mod)
        if(y&1) ret=ret*x%mod;
    return ret;
}
void dfs(int u,int p,ll sum) {
    sum=sum*pw(cnt[u],mod-2)%mod;
    ans=(ans+tot*sum)%mod;
    sum=(sum+pw(cnt[u],mod-2))%mod;
    for(int& v: g[u]) if(v!=p) {
        dfs(v,u,sum);
    }
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n;
    for(int u,v,i=1;i<n;i++) {
        cin>>u>>v;
        g[u].pb(v),g[v].pb(u);
    }
    dfs1(1,0);
    dfs(1,0,0);
    cout<<ans;
    return 0;
}