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

this54 · 2025-06-30 22:14:35 · 题解

关于我在考场上乱搞换根 dp 这件事。

分析题意

很明显，题目中所谓的遇到新的点就写下编号这一步其实就是 dfs 序。于是题目就在问给定一颗无根树，不限定初始节点与子节点访问顺序时，这个树的 dfs 序有多少种。

从一个点切入

首先这个题目不限定初始节点就很难受，即使我们能 O(n) 计算 dfs 序，最终还是超时的。先尝试从一个点开始的 dfs 序数量切入。我们可以用递归的表达式表示以 i 为子树根时的所有 dfs 序数量，称之为 sum_i 。令 siz_i 为 i 节点的子节点个数，对于这个节点，它可以按照任意顺序访问子节点，所以有 siz_i! 种访问方式，而每个子节点 j 又有 sum_j 种结果，所以可以得到 sum_i = siz_i! \times \prod_{j = 1}^{siz_i} sum_{son_{i,j}} 这个式子，不难发现展开后最终根的结果就是所以节点的子节点的个数的阶乘的乘积（即 \prod_{i = 1}^{n} siz_i! ）。

最终正解

现在我们解决了一个点为根时的问题，那么怎么解决所有问题呢？

我们从树的性质入手，一颗树除根节点以外都有父亲节点，所以非根个节点子节点个数就等于其度数减 1 ，我们先整一个最终和的结果表示出来，ans = \sum_{i = 1}^{n} (deg_i \times \prod_{j = 1}^{n} siz_j!) = \sum_{i = 1}^{n} deg_i \prod_{i = 1}^{n} siz_i!，所以这就是我们最终的答案（ deg_i 表示 i 的度）。

代码

#include <bits/stdc++.h>
#define N 100010
#define mod 1000000000
#define ll long long
using namespace std;
int n;
ll deg[N];
ll prod = 1, sum;
ll p[N];
int main()
{
    cin >> n;
    if (n == 1) return (puts("1"), 0);
    static int u, v;
    p[0] = 1;
    for (int i = 1; i < n; i++) cin >> u >> v, deg[u]++, deg[v]++, p[i] = (p[i - 1] * i) % mod;
    for (int i = 1; i <= n; i++) prod = (prod * p[deg[i] - 1]) % mod, sum = (sum + deg[i]) % mod;
    cout << (prod * sum) % mod;
    return 0;
}

最后，一定要注意特判 n == 1的情况，否则你会因为子节点个数被减到 -1 而结果错误。