Codeforces #564 (Div. 2) D. Nauuo and Circle[树形DP]

题目链接:http://codeforces.com/contest/1173/problem/D

解题思路:

首先得知道按照圆周顺序的话，那么一颗子树必须存放在连续的一段区间里面，现在我们假设根节点是1，那么一颗为u做根节点的子树他的方案数就是各个儿子的方案数的乘积最后再乘以儿子个数+1(u节点本身)的排列方案数。

所以最后答案很明显是每个节点的度的阶乘的乘积，然后由于有n个点可以做为根节点，所以答案还要乘以n。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int mx = 2e5 + 10;
int du[mx];
int main()
{
	int n;
	scanf("%d",&n);
	ll ans = n;
	int u,v;
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		du[u]++,du[v]++;
		ans = ans*du[u]%mod;
		ans = ans*du[v]%mod;
	}
	printf("%lld\n",ans);
	return 0;
}