A50544.BFS 题解

题目是一棵树，还求方案数量，还求任意根的方案数量，这是明显的换根 DP 啊！

过程就是一般的换根 DP 的过程。定义 $dp_u$ 为对于树根节点为 $u$ 的时候，子树大小的乘积。状态转移也不是很难得到，如下：

$$dp_v=\cfrac{dp_u \times (n-size_v)}{size_v} \bmod 998244353$$

容易发现需要逆元处理。注意到 $998244353$ 是质数，且 $size_v$ 不可能是其倍数，所以直接运用费马小定理即可。用快速幂实现。

定义 $ans_i$ 为根节点为 $i$ 的随机 BFS 序数量。发现其刚好为有根树的拓扑序数量。得到结论：$ans_i=\cfrac{n!}{dp_i} \bmod 998244353$.

预处理 $n!$，并使用快速幂计算逆元。

时间复杂度：$O(n \log 998244353)$.

空间复杂度：$O(n)$.

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e6+16,MOD=998244353;
struct node{
    ll nxt,to;
};
ll n,u,v,tot;
ll hd[MAXN],siz[MAXN],dp[MAXN],fac[MAXN],ans[MAXN];
node edge[MAXN<<1];
inline void add(const ll &u,const ll &v){
	edge[++tot]={hd[u],v};
	hd[u]=tot;
	return;
}
inline ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}
inline void dfs1(const ll &u,const ll &fath){
    ll v;
	siz[u]=1;
	for(ll i=hd[u];i;i=edge[i].nxt){
		v=edge[i].to;
		if(v^fath){
            dfs1(v,u);
            siz[u]+=siz[v];
        }
	}
	return;
}
inline void dfs2(const ll &u,const ll &fath){
    ll v;
	for(ll i=hd[u];i;i=edge[i].nxt){
		v=edge[i].to;
		if(v==fath) continue;
		dp[v]=dp[u]*(n-siz[v])%MOD*qpow(siz[v],MOD-2)%MOD;
		dfs2(v,u);
	}
	return;
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<n;i++){
		scanf("%lld %lld",&u,&v);
		add(u,v);
        add(v,u);
	}
	dfs1(1,0);
	fac[0]=1;
	for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
	dp[1]=1;
	for(ll i=1;i<=n;i++) dp[1]=dp[1]*siz[i]%MOD;
	dfs2(1,0);
	for(ll i=1;i<=n;i++) ans[i]=fac[n]*qpow(dp[i],MOD-2)%MOD;
	for(ll i=1;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}