Codeforces Round #564 (Div. 2) D(组合数学/树上DP)

本文主要是介绍Codeforces Round #564 (Div. 2) D(组合数学/树上DP)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

D. Nauuo and Circle

题意：
  给定一棵\(n\)个节点的树，从\(1\)到\(n\)编号，现在你需要玩弄这棵树。问按照顺时针遍历能获得多少种不同的序列。最后的答案对\(\%998244353\)
思路：
  定义\(son[u]\)表示\(u\)的子节点的个数。先固定\(1\)是这个序列中的第一个，因为这是一个环所以最后的答案要乘上\(n\)。定义\(dp[u]\)表示的是以\(u\)为节点的方案数。
  对于节点\(1\),我们可以就是对\(son[u]\)进行全排列，并将排列方式放在\(1\)的后面，将\(son[u]\)全排列一共有\(A_{son[u]} ^ {son[u]}\)种方案，也就是\(son[u]!\)种方案，而它的每一个儿子\(v\)同样也有它们的子节点，所以就得到了式子$$dp[u] = son[u]! * \prod_{v\in G[u]}{dp[v]}$$
而对于非\(1\)节点，它们自身也可以进行全排列所以对于非\(1\)的节点，它们的方案数的表达式是\(dp[u] = (son[u] + 1)! * \prod_{v\in G[u]}{dp[v]}\)
所以最后我们将两种情况合并就是$$dp[u] = du[u]! \prod_{v\in G[u]}{dp[v]}$$其中\(du[u]\)表示的是\(du[u]\)的度

void solve() {
	int n;
	std::cin >> n;
	fac[0] = 1;
	rep(i,1,N) fac[i] = fac[i - 1] * i;
	std::vector<int> G[n + 1], du(n + 1);
	rep(i,0,n - 1) {
		int u, v;
		std::cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
		du[v] ++, du[u] ++;
	}

	std::vector<Z> dp(n + 1);

	std::function<void(int, int)> dfs = [&] (int u, int fa) -> void {
		Z res = 1;
		for (auto v : G[u]) {
			if (v == fa) continue;
			dfs(v, u);
			res = res * dp[v];
		}
		dp[u] = fac[du[u]] * res;
	};

	dfs(1, 0);
	Z ans = dp[1] * n;
	std::cout << ans.val() << "\n";
}

这篇关于Codeforces Round #564 (Div. 2) D(组合数学/树上DP)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！