ouuan 的博客

ouuan 的博客

题解 CF1172B 【Nauuo and Circle】

posted on 2019-06-08 13:51:44 | under 题解 |

考虑 DP,令 $f_u$ 为子树 $u$ 方案数,那么 $f_u=(|son(u)| + [u\ne root])!\prod\limits_{v\in son(u)}f_v$ , $ans = nf_{root}$ 。(先固定根的位置,每棵子树要为儿子排位置,如果非根自己也要参与排位置,然后再画子树。)

事实上不需要 DP,答案为每个点的度数阶乘之积乘上 $n$ 。

#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;
}