题解 P13020 [GESP202506 八级] 遍历计数
题目分析
题目要求计算一棵树所有可能的 DFS 遍历序列数量。由于 DFS 的起点选择和子节点遍历顺序都是任意的，因此需要考虑所有可能的排列组合。并且根是不确定的，所以考虑换根 DP
算法思路
采用树形 DP 来解决这个问题，主要分为两个 DFS 过程：
-
状态定义：
f[x]：以x为根的子树，不考虑父节点时的DFS序列数dp[x]：以x为根的子树，考虑父节点时的DFS序列数cnt[x]：x的子节点数量
-
转移方程：
-
f_x = \prod_{y\in son_x}dp_y -
-
完整代码
#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;
}复杂度分析
时间复杂度
空间复杂度：