专栏文章

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

tthis54
P13020题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip0blvc
此快照首次捕获于
2025/12/03 04:04
3 个月前
此快照最后确认于
2025/12/03 04:04
3 个月前
查看原文
关于我在考场上乱搞换根 dpdp 这件事。

分析题意

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

从一个点切入

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

最终正解

现在我们解决了一个点为根时的问题，那么怎么解决所有问题呢？
我们从树的性质入手，一颗树除根节点以外都有父亲节点，所以非根个节点子节点个数就等于其度数减 11 ，我们先整一个最终和的结果表示出来，ans=∑i=1n(degi×∏j=1nsizj!)=∑i=1ndegi∏i=1nsizi!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!，所以这就是我们最终的答案（ degideg_i 表示 ii 的度）。

代码

CPP
#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-1 而结果错误。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...