fork(17) download
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3.  
  4. #define LL long long
  5. #define MOD 1000000007
  6. #define MAXN 100005
  7.  
  8. LL SubTree[MAXN],TopoCount[MAXN],Fact[MAXN],Inv[MAXN];
  9. vector<int> adj[MAXN] ;
  10. int N,T,U,V;
  11. LL inv(LL a,LL b){
  12. LL res = 1 ;
  13. a %= MOD ;
  14. while(b){
  15. if(b%2){
  16. res = (res*a)%MOD ;
  17. }
  18. a = (a*a)%MOD ;
  19. b /= 2 ;
  20. }
  21. return res%MOD ;
  22. }
  23. void pre(){
  24. Fact[0] = 1 ;
  25. Inv[0] = 1 ;
  26. for(int i=1;i<MAXN;i++){
  27. Fact[i] = (1LL * Fact[i-1] * i)%MOD ;
  28. assert(Fact[i] >= 0) ;
  29. }
  30. for(int i=1;i<MAXN;i++){
  31. Inv[i] = inv(Fact[i],MOD-2) ;
  32. assert(Inv[i] >= 0) ;
  33. }
  34. }
  35.  
  36.  
  37.  
  38. LL nCr(int N,int R){
  39. return (1LL * Fact[N] * (1LL * Inv[N-R] * Inv[R])%MOD )%MOD ;
  40. }
  41.  
  42.  
  43. void dfs(int u,int p=-1){
  44.  
  45. SubTree[u] = 1 ;
  46. TopoCount[u] = 1 ;
  47. for(vector<int> :: iterator it = adj[u].begin();it!=adj[u].end();++it){
  48. if(*it != p){
  49. dfs(*it,u) ;
  50. SubTree[u] += SubTree[*it] ;
  51. }
  52. }
  53. int subtree = (SubTree[u]-1) ;
  54. for(vector<int> :: iterator it = adj[u].begin();it!=adj[u].end();++it){
  55.  
  56. if(*it != p){
  57. dfs(*it,u) ;
  58. LL x = (1LL * nCr(subtree,SubTree[*it]) * TopoCount[*it])%MOD ;
  59. TopoCount[u] = (1LL * TopoCount[u] * x)%MOD ;
  60. subtree -= SubTree[*it] ;
  61. }
  62. }
  63. }
  64. int main(){
  65.  
  66.  
  67. pre() ;
  68. scanf("%d",&T) ;
  69. while(T--){
  70. scanf("%d",&N) ;
  71. for(int i=1;i<N;i++){
  72. scanf("%d%d",&U,&V) ;
  73. adj[U].push_back(V) ;
  74. adj[V].push_back(U) ;
  75. }
  76. dfs(1) ;
  77. printf("%lld\n",TopoCount[1]%MOD) ;
  78. for(int i=1;i<=N;i++)
  79. adj[i].clear() ;
  80. memset(SubTree,0,sizeof SubTree) ;
  81. memset(TopoCount,0,sizeof TopoCount) ;
  82. }
  83. return 0 ;
  84. }
  85.  
  86.  
Success #stdin #stdout 0.19s 7576KB
stdin
3
3
1 2
2 3
3
1 2
1 3
4
1 2
2 3
1 4
stdout
1
2
3