题解 CF1172B 【Nauuo and Circle】

ouuan

2019-06-08 13:51:44

Solution

考虑 DP,令 $f_u$ 为子树 $u$ 方案数,那么 $f_u=(|son(u)| + [u\ne root])!\prod\limits_{v\in son(u)}f_v$,$ans = nf_{root}$。(先固定根的位置,每棵子树要为儿子排位置,如果非根自己也要参与排位置,然后再画子树。) 事实上不需要 DP,答案为每个点的度数阶乘之积乘上 $n$。 ```cpp #include <iostream> #include <cstdio> using namespace std; typedef long long ll; const int N = 200010; const int mod = 998244353; int n, ans, d[N]; int main() { int i, u, v; scanf("%d", &n); ans = n; for (i = 1; i < n; ++i) { scanf("%d%d", &u, &v); ans = (ll) ans * (++d[u]) % mod * (++d[v]) % mod; } cout << ans; return 0; } ```