B. Nauuo and Circle

90 阅读 0 评论 60 点赞

我是靠谱客的博主迅速书包，最近开发中收集的这篇文章主要介绍B. Nauuo and Circle，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接:http://codeforces.com/problemset/problem/1172/B

Nauuo is a girl who loves drawing circles.

One day she has drawn a circle and wanted to draw a tree on it.

The tree is a connected undirected graph consisting of nn nodes and n−1n−1 edges. The nodes are numbered from 11 to nn.

Nauuo wants to draw a tree on the circle, the nodes of the tree should be in nn distinct points on the circle, and the edges should be straight without crossing each other.

"Without crossing each other" means that every two edges have no common point or the only common point is an endpoint of both edges.

Nauuo wants to draw the tree using a permutation of nn elements. A permutation of nn elements is a sequence of integers p1,p2,…,pnp1,p2,…,pn in which every integer from 11 to nn appears exactly once.

After a permutation is chosen Nauuo draws the ii-th node in the pipi-th point on the circle, then draws the edges connecting the nodes.

The tree is given, Nauuo wants to know how many permutations are there so that the tree drawn satisfies the rule (the edges are straight without crossing each other). She only wants to know the answer modulo 998244353998244353, can you help her?

It is obvious that whether a permutation is valid or not does not depend on which nn points on the circle are chosen.

Input

The first line contains a single integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of nodes in the tree.

Each of the next n−1n−1 lines contains two integers uu and vv (1≤u,v≤n1≤u,v≤n), denoting there is an edge between uu and vv.

It is guaranteed that the given edges form a tree.

Output

The output contains a single integer — the number of permutations suitable to draw the given tree on a circle satisfying the rule, modulo 998244353998244353.

Examples

input

Copy

output

Copy

input

Copy

output

Copy

Note

Example 1

All valid permutations and their spanning trees are as follows.

Here is an example of invalid permutation: the edges (1,3)(1,3) and (2,4)(2,4) are crossed.

Example 2

Every permutation leads to a valid tree, so the answer is 4!=244!=24.

题意：给一棵树，然后要用节点画一个圈，顶点之间的边不能相交。

思路：画画图就可以知道有同一个父节点的子节点必须要连续，然后就是算组合数，考虑一个顶点他有x个子节点，那么字节点的排列数有x!,然后父亲节点可以放x+2个位置(除顶点外)，但每个顶点都可以作为第一个开始的数，所以最后要乘以个n;所以公式为n*de[i](i从1到n)，de[i]为每个节点的度。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#define LL long long

using namespace std;
const int maxn=2e5+100;
const int mod=998244353;

LL fac[maxn];
int de[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    fac[0]=1;
    for(int i=1;i<=n;i++)
    {
        fac[i]=fac[i-1]*i;
        fac[i]%=mod;
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        de[u]++;
        de[v]++;
    }
    LL ans=n;
    for(int i=1;i<=n;i++)
    {
        ans=ans%mod*fac[de[i]]%mod;
        ans%=mod;
    }
    printf("%lldn",ans);
    return 0;
}

反思：组合数还是太弱。