fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  3. #define endl "\n"
  4. #define int long long
  5. using namespace std;
  6. void SieveOfEratosthenes(int n, bool prime[], 
  7. 						bool primesquare[], int a[]) 
  8. { 
  9. 	// Create a boolean array "prime[0..n]" and 
  10. 	// initialize all entries it as true. A value 
  11. 	// in prime[i] will finally be false if i is 
  12. 	// Not a prime, else true. 
  13. 	for (int i = 2; i <= n; i++) 
  14. 		prime[i] = true; 
  15.  
  16. 	// Create a boolean array "primesquare[0..n*n+1]" 
  17. 	// and initialize all entries it as false. A value 
  18. 	// in squareprime[i] will finally be true if i is 
  19. 	// square of prime, else false. 
  20. 	for (int i = 0; i <= (n * n + 1); i++) 
  21. 		primesquare[i] = false; 
  22.  
  23. 	// 1 is not a prime number 
  24. 	prime[1] = false; 
  25.  
  26. 	for (int p = 2; p * p <= n; p++) { 
  27. 		// If prime[p] is not changed, then 
  28. 		// it is a prime 
  29. 		if (prime[p] == true) { 
  30. 			// Update all multiples of p 
  31. 			for (int i = p * 2; i <= n; i += p) 
  32. 				prime[i] = false; 
  33. 		} 
  34. 	} 
  35.  
  36. 	int j = 0; 
  37. 	for (int p = 2; p <= n; p++) { 
  38. 		if (prime[p]) { 
  39. 			// Storing primes in an array 
  40. 			a[j] = p; 
  41.  
  42. 			// Update value in primesquare[p*p], 
  43. 			// if p is prime. 
  44. 			primesquare[p * p] = true; 
  45. 			j++; 
  46. 		} 
  47. 	} 
  48. } 
  49.  
  50. // Function to count divisors 
  51. int countDivisors(int n) 
  52. { 
  53. 	// If number is 1, then it will have only 1 
  54. 	// as a factor. So, total factors will be 1. 
  55. 	if (n == 1) 
  56. 		return 1; 
  57.  
  58. 	bool prime[n + 1], primesquare[n * n + 1]; 
  59.  
  60. 	int a[n]; // for storing primes upto n 
  61.  
  62. 	// Calling SieveOfEratosthenes to store prime 
  63. 	// factors of n and to store square of prime 
  64. 	// factors of n 
  65. 	SieveOfEratosthenes(n, prime, primesquare, a); 
  66.  
  67. 	// ans will contain total number of distinct 
  68. 	// divisors 
  69. 	int ans = 1; 
  70.  
  71. 	// Loop for counting factors of n 
  72. 	for (int i = 0;; i++) { 
  73. 		// a[i] is not less than cube root n 
  74. 		if (a[i] * a[i] * a[i] > n) 
  75. 			break; 
  76.  
  77. 		// Calculating power of a[i] in n. 
  78. 		int cnt = 1; // cnt is power of prime a[i] in n. 
  79. 		while (n % a[i] == 0) // if a[i] is a factor of n 
  80. 		{ 
  81. 			n = n / a[i]; 
  82. 			cnt = cnt + 1; // incrementing power 
  83. 		} 
  84.  
  85. 		// Calculating number of divisors 
  86. 		// If n = a^p * b^q then total divisors of n 
  87. 		// are (p+1)*(q+1) 
  88. 		ans = ans * cnt; 
  89. 	} 
  90.  
  91. 	// if a[i] is greater than cube root of n 
  92.  
  93. 	// First case 
  94. 	if (prime[n]) 
  95. 		ans = ans * 2; 
  96.  
  97. 	// Second case 
  98. 	else if (primesquare[n]) 
  99. 		ans = ans * 3; 
  100.  
  101. 	// Third casse 
  102. 	else if (n != 1) 
  103. 		ans = ans * 4; 
  104.  
  105. 	return ans; // Total divisors 
  106. } 
  107.  
  108.  
  109. void addEdge(vector<int> v[], 
  110. 			int x, 
  111. 			int y) 
  112. { 
  113. 	v[x].push_back(y); 
  114. 	v[y].push_back(x); 
  115. } 
  116.  
  117. // A function to print the path between 
  118. // the given pair of nodes. 
  119. int ans =1;
  120. void printPath(vector<int> stack, int A[]) 
  121. { 
  122. 	int i; 
  123.  
  124. 	for (i = 0; i < (int)stack.size() - 1; 
  125. 		i++) { 
  126. 	//	cout << stack[i] << " -> "; 
  127. 		ans = ans* A[stack[i]-1];
  128. 	} 
  129. //	cout << stack[i]; 
  130. 	ans = ans*A[stack[i]-1];
  131. 	ans = countDivisors(ans);
  132. } 
  133.  
  134. // An utility function to do 
  135. // DFS of graph recursively 
  136. // from a given vertex x. 
  137. void DFS(vector<int> v[], 
  138. 		bool vis[], 
  139. 		int x, 
  140. 		int y, 
  141. 		vector<int> stack, int A[]) 
  142. { 
  143. 	stack.push_back(x); 
  144. 	if (x == y) { 
  145.  
  146. 		// print the path and return on 
  147. 		// reaching the destination node 
  148. 		printPath(stack, A); 
  149. 		return; 
  150. 	} 
  151. 	vis[x] = true; 
  152.  
  153. 	// A flag variable to keep track 
  154. 	// if backtracking is taking place 
  155. 	int flag = 0; 
  156. 	if (!v[x].empty()) { 
  157. 		for (int j = 0; j < v[x].size(); j++) { 
  158. 			// if the node is not visited 
  159. 			if (vis[v[x][j]] == false) { 
  160. 				DFS(v, vis, v[x][j], y, stack, A); 
  161. 				flag = 1; 
  162. 			} 
  163. 		} 
  164. 	} 
  165. 	if (flag == 0) { 
  166.  
  167. 		// If backtracking is taking 
  168. 		// place then pop 
  169. 		stack.pop_back(); 
  170. 	} 
  171. } 
  172.  
  173. // A utility function to initialise 
  174. // visited for the node and call 
  175. // DFS function for a given vertex x. 
  176. void DFSCall(int x, 
  177. 			int y, 
  178. 			vector<int> v[], 
  179. 			int n, 
  180. 			vector<int> stack, int A[]) 
  181. { 
  182. 	// visited array 
  183. 	bool vis[n + 1]; 
  184.  
  185. 	memset(vis, false, sizeof(vis)); 
  186.  
  187. 	// DFS function call 
  188. 	DFS(v, vis, x, y, stack, A); 
  189. } 
  190.  
  191.  
  192. int32_t main() {
  193. 		int t;
  194. 		cin>>t;
  195. 		while(t--){
  196. 		 int n;
  197. 		    cin>>n;
  198. 		    vector<int> v[n+1], stack; 
  199.  
  200. 		    int a, b;
  201. 	        for(int i=0; i<n-1; i++){
  202. 	            cin>>a>>b;
  203. 	            addEdge(v, a, b);
  204. 	        }
  205.  
  206. 	        int A[n];
  207.  
  208. 	        for(int i=0; i<n; i++) cin>>A[i];
  209.  
  210. 	        int q, source, dest; cin>>q;
  211.  
  212. 	        for(int i=0; i<q; i++){
  213. 	            cin>>source>>dest;
  214. 	            ans = 1;
  215. 	            DFSCall(source, dest, v, n+1, stack, A);
  216. 	             cout<<ans;   cout<<endl;
  217. 		 }	}
  218.   return 0; 
  219. } 
  220.  
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
1
5
1 2
1 3
2 4
2 5
2 6 4 3 5
2
1 4
2 2
stdout
copy 
9
4
https://ideone.com/ifSlDG
language:
C++14 (gcc 8.3)
created:
4 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!