题解：CF1172B Nauuo and Circle

cjrqwq · 2025-01-01 19:37:48 · 题解

首先，观察样例，发现真正不同的只有 4 个， 也就是圆心正上方的数是 1 的情况，剩下的都是旋转得到的。所以以 1 为根讨论，最后输出 ans \times n 。

手玩一下，发现连边就会将各个子树隔绝，所以一个子树的排布是要连续的。而且所有的子树，最终是不会留下空位的。

我们定义 f_u 为以 u 为根的子树的方案数，有 d_u 个子树。那么它们可以随意排列，贡献就是 (d_u +1)!，每个子树的方案数也是独立的。所以有：

我们已经把节点 1 固定了，没有考虑 u 节点，如果不是根的话，节点 u 也可以和它的子树一起排列，这种情况下，上面式子的 d_u 要变成 (d_u + 1)。

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e5+10, mod = 998244353;
int fac[N],n;
vector<int>e[N];

int f[N];
void dfs(int u,int fa) {
    f[u] = fac[e[u].size()];
    for(int v:e[u]) {
        if(v == fa) continue;
        dfs(v,u);
        f[u] = 1ll * f[u] * f[v] % mod; 
    }
}
int main() {
    cin>>n;
    fac[0] = 1;
    for(int i=1;i<=n;i++) fac[i] = 1LL * fac[i-1] * i % mod;
    for(int i=1,u,v;i<n;i++) cin>>u>>v, e[u].push_back(v), e[v].push_back(u);
    dfs(1,1);
    cout << 1ll * f[1] * n % mod;
    return 0;
}