题解：P16355 「Diligent-OI R3 C」彼方へ、名もなき海辺より
jkl_code_chncfd
·
·
题解
题意简述
给定一棵 n 个结点的有根树（根为 1）。对每个点 u 独立地选一个祖先或儿子连一条无向边（允许重边）。求所有可能的新图的连通块个数之和，对 998244353 取模。
核心转化
每个点恰有一条出边，新图弱连通块数 = 有向环个数。总方案数 T = \prod_{u} \deg(u)，其中 \deg(u) = \text{depth}(u) + \text{soncnt}(u)。
设 \operatorname{inv}(u) = \deg(u)^{-1}，则答案 = T \cdot \sum_{C} \prod_{u\in C} \operatorname{inv}(u)，求和遍及所有有向环。
树形 DP
令 f(u) = 1 + \sum_{v\in \text{son}(u)} \operatorname{inv}(v)\cdot f(v) 表示从 u 出发向上跳任意次（含空路径）的权值和。
令 s(u) = \sum_{v\in \text{son}(u)} \operatorname{inv}(v)\cdot f(v)。
则 \sum_{C} \prod_{u\in C} \operatorname{inv}(u) = \sum_{u} \operatorname{inv}(u)\cdot s(u)。
答案 = T \cdot \sum_{u} \operatorname{inv}(u)\cdot s(u) \bmod 998244353。
时间复杂度
## **代码**
```cpp
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define pb push_back
using namespace std;
int n,deg[500010],inv[500010],d[500010],f[500010],s[500010],tot=1,ans,cur;
vi g[500010],ch[500010];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%998244353;
a=a*a%998244353,b>>=1;
}
return res;
}
void dfs1(int u,int fa,int c){
d[u]=c;
int cnt=0;
for(int v:g[u]){
if(v==fa)continue;
ch[u].pb(v),cnt++;
dfs1(v,u,c+1);
}
deg[u]=c+cnt,tot=tot*deg[u]%998244353,inv[u]=qpow(deg[u],998244351);
}
void dfs2(int u){
s[u]=0;
for(int v:ch[u]){dfs2(v);s[u]=(s[u]+inv[v]*f[v])%998244353;}
f[u]=(s[u]+1)%998244353,ans=(ans+inv[u]*s[u])%998244353;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1,u,v;i<n;i++)cin>>u>>v,g[u].pb(v),g[v].pb(u);
dfs1(1,0,0);
dfs2(1);
cout<<tot*ans%998244353;
return 0;
}
```