题目描述
我们都知道
树的dfs序是一棵树从根节点出发，dfs遍历时依次经过的节点序列。
现在猫猫有一棵包含n个结点的有根树，结点从1~n编号，1号点为根节点。猫猫想让你告诉它，这棵树的dfs序有多少种。
由于答案很大，你需要对998244353取模。
输入
第一行一个正整数n(1≤n≤2×105)表示节点数。
接下来n-1行，每行两个整数u,v（1≤u,v≤2×105且u≠v）表示树上的一条边 (u,v)。
输出
输出一个整数，表示这棵树dfs序的个数。
样例输入 Copy
5
1 2
1 4
2 3
2 5
样例输出 Copy
4
如图 ，dfs序有[1,2,3,5,4],[1,2,5,3,4],[1,4,2,3,5],[1,4,2,5,3] 共4种。
对于树的dfs序列来说，他的dfs序总数等于他的每个子节点的dfs序相乘再乘他的子序列的全排列的个数(阶乘)，所以可以用dfs从子节点往上求，递推出根节点的dfs序总数。
点击查看代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
ll f[N], ans[N];
vector<int>g[N];
void init()
{
f[0] = 1;
for (int i = 1; i <= N; i++)
{
f[i] = i * f[i - 1] % mod;
}
}//f代表阶乘
void dfs(int u, int fa)//fa标记父节点
{
ans[u] = 1;//对于一个节点本身自己的(如果没有子节点)dfs序就是1；
for (auto v : g[u])
{
if (v == fa)continue;//遍历到父节点就跳过
dfs(v, u);//往下遍历，把u作为父节点
ans[u] = ans[u] * ans[v] % mod;//更新a[u]
}
ans[u] = ans[u] * f[g[u].size() - 1] % mod;//乘子节点的全排列，但是g[u]中有一个是和父节点相连，故还需要-1
}
int main()
{
int i, j, n;
cin >> n;
init();
for (i = 1; i < n; i++)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);//未知谁是父亲节点
}
g[1].push_back(-1);//因为1没有父节点，我们假设-1是他的父节点
dfs(1, -1);
cout << ans[1];
return 0;
}