题解 P13020 [GESP202506 八级] 遍历计数

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int M=1e5+5,mod=1e9;
int n,res,fac[M],f[M],dp[M],cnt[M];
vector<int>g[M],R[M];
// g[]存储树的邻接表，R[]用于存储后缀积

// 预处理阶乘数组
inline void init() {
	fac[0] = 1;
	for(int i=1;i<=n;++i)
		fac[i] = fac[i-1] * i % mod;
}

inline void dfs1(int x,int fa) {
	f[x] = dp[x] = 1;
	for(auto y:g[x]) {
		if(y == fa) continue;
		dfs1(y, x), cnt[x]++;
		(f[x] *= dp[y]) %= mod;
	} 
	dp[x] = f[x] * fac[cnt[x]] % mod;
	// 子树排列方式数目为f[x]乘以子节点数目的阶乘
}

inline void dfs2(int x,int fa,int val) {
	// 计算当前节点作为根的总遍历方式数目并累加到结果中
	if(x == 1) (res += dp[x]) %= mod;
	else (res += f[x] * val % mod * fac[cnt[x]+1] % mod) %= mod;

	// 预处理后缀积数组R，用于快速计算右侧兄弟子树的贡献
	for(int i=0;i<=g[x].size();++i)
		R[x].emplace_back(1);
	for(int i=g[x].size()-1;i>=0;--i) {
		if(g[x][i] == fa) R[x][i] = R[x][i+1];
		else R[x][i] = R[x][i+1] * dp[g[x][i]] % mod;
	}
	
	int L = 1; // 前缀积
	for(int i=0;i<g[x].size();++i) {
		int y = g[x][i];
		if(y == fa) continue;

		// 计算传递给子节点的信息：左侧兄弟子树的贡献 L * 右侧兄弟子树的贡献 R[i+1] * 父节点信息 val
		if(x == 1) dfs2(y, x, L * R[x][i+1] % mod * fac[cnt[x]-1] % mod);
		else dfs2(y, x, L * R[x][i+1] % mod * fac[cnt[x]] % mod * val % mod);
		
		(L *= dp[y]) %= mod;
	} 
}

signed main() {
	scanf("%lld", &n),init();

	// 读入树的边，构建邻接表
	for(int i=1,u,v;i<n;++i) {
		scanf("%lld%lld", &u, &v);
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}

	// 两次DFS处理
	dfs1(1, 0); // 以节点1为根进行第一次DFS
	dfs2(1, 0, 0); // 以节点1为根进行第二次DFS

	printf("%lld", res); // 输出结果
	return 0;
}