fork(17) download
copy 
  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
comments (?)
stdin
copy 
3
3
1 2
2 3
3
1 2
1 3
4
1 2
2 3
1 4
stdout
copy 
1
2
3
https://ideone.com/cl9E09
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!