A27133. 遍历计数
填空题
困难
知识点
题目描述
遍历计数
题目描述
给定一棵有n个结点的树T，结点依次以1,2,...,n标号。树T的深度优先遍历序可由以下过程得到:
1.选定深度优先遍历的起点s(1≤s≤n)，当前所在结点即是起点。
2.若当前结点存在未被遍历的相邻结点u则遍历u，也即令当前所在结点为u并重复这一步;否则回溯。
3.按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。
第一步中起点的选择是任意的，并且第二步中遍历相邻结点的顺序是任意的，因此对于同一棵树T可能有多组不同的深度优先遍历序。请你求出树T有多少组不同的深度优先遍历序。由于答案可能很大，你只需要求出答案对 109取模之后的结果。
输入格式
第一行，一个整数 n，表示树 T的结点数。
接下来n-1行，每行两个正整数ui,vi，表示树T中的一条连接结点ui,vi的边。
输出格式
输出一行，一个整数，表示树T的不同的深度优先遍历序数量对 109取模的结果。
样例
输入样例 1
4
1 2
2 3
3 4输出样例 1
6输入样例 2
8
1 2
1 3
1 4
2 5
2 6
3 7
3 8输出样例 2
112数据范围
对于40%的测试点，保证1≤n≤8。
对于另外20%的测试点，保证给定的树是一条链。
对于所有测试点，保证1≤n≤105。
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5 +5;
const int mod = 1e9;
int n, deg[N], fac[N];
int pre[N], suf[N];
int ans;
int main(){
scanf("%d"，&n);
fac[0]= 1;
for(int i =1; i<= n; i++)
fac[i]=1ll*fac[i- 1]*i % mod;
for(int i=1;i<n; i++){
int u, v;
scanf("%d%d"，&u, &v);
deg[u]++;
deg[v]++;
}
pre[0]= 1;
for(int i=1; i<= n; i++)
pre[i]=1ll*pre[i-1]*fac[deg[i]- 1]% mod;
suf[n +1]= 1;
for(int i=n; i; i--)
suf[i]= 1ll*suf[i + 1]* fac[deg[i]- 1]% mod;
for(int i=1; i<= n; i++)
ans =(ans+ 1ll*pre[i-1]* fac[deg[i]]% mod * suf[i + 1])%mod;
printf("%d\n",ans);
return 0:
}
上一题
下一题