fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define int long long
  4. #ifdef LOCAL
  5. #define watch(x) cout << #x << ':' << x << ' ';
  6. #else
  7. #define watch(x) 0
  8. #endif
  9. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  10. #define mod 1000000007
  11. #define pb push_back
  12. #define ff first
  13. #define ss second
  14. #define sz(x) ((int)(x).size())
  15. #define all(x) (x).begin(), (x).end()
  16. #define rall(x) (x).rbegin(), (x).rend()
  17. typedef long long ll;
  18. typedef unsigned long long ull;
  19. typedef long double lld;
  20.  
  21. void init() {
  22. #ifdef LOCAL
  23. 	freopen("in.txt", "r", stdin);
  24. 	freopen("out.txt", "w", stdout);
  25. 	freopen("err.txt", "w", stderr);
  26. #endif
  27. }
  28.  
  29. vector<int> v[30010], val, sieve, ans;
  30. vector<map<int, int>> hmm;
  31. int n;
  32.  
  33. void precomp() {
  34. 	sieve = vector<int>(1000010);
  35. 	for (int i = 0; i <= 1000000; i++) {
  36. 		sieve[i] = i;
  37. 	}
  38. 	sieve[0] = sieve[1] = 0;
  39.  
  40. 	for (int i = 2; i <= 1000000; i++) {
  41. 		if (sieve[i] == i) {
  42. 			for (int j = i * i; j <= 1000000; j += i) {
  43. 				sieve[j] = min(sieve[j], i);
  44. 			}
  45. 		}
  46. 	}
  47. }
  48.  
  49. void dfs(int x, int p) {
  50. 	int z = val[x], d = sieve[val[x]];
  51. 	while (z > 1) {
  52. 		int c = 0;
  53. 		while (z % d == 0) {
  54. 			c++;
  55. 			z /= d;
  56. 		}
  57. 		hmm[x].insert({d, c});
  58. 		d = sieve[z];
  59. 	}
  60.  
  61. 	for (int y : v[x]) {
  62. 		if (y != p) {
  63. 			dfs(y, x);
  64.  
  65. 			if (sz(hmm[x]) < sz(hmm[y])) {
  66. 				swap(hmm[x], hmm[y]);
  67. 			}
  68.  
  69. 			for (auto r : hmm[y]) {
  70. 				int a = r.ff;
  71. 				int b = r.ss;
  72.  
  73. 				if (hmm[x].count(a)) {
  74. 					hmm[x][a] += b;
  75. 				}
  76. 				else hmm[x][a] = b;
  77. 			}
  78. 		}
  79. 	}
  80.  
  81. 	int c = 1;
  82. 	for (auto w : hmm[x]) {
  83. 		c = (c * (w.ss + 1)) % mod;
  84. 	}
  85. 	ans[x] = c;
  86. }
  87.  
  88. int32_t main()
  89. {
  90. 	IOS;
  91. 	init();
  92. 	int t = 1;
  93. 	precomp();
  94. 	cin >> t;
  95.  
  96. 	while (t--)
  97. 	{
  98. 		cin >> n;
  99. 		for (int i = 0; i <= n; i++) v[i].clear();
  100. 		val.assign(n + 1, 0);
  101. 		hmm.assign(n + 1, {});
  102. 		ans.assign(n + 1, 0);
  103.  
  104. 		for (int i = 0; i < n; i++) cin >> val[i + 1];
  105. 		int a, b;
  106. 		for (int i = 0; i < n - 1; i++) {
  107. 			cin >> a >> b;
  108. 			v[a].pb(b);
  109. 			v[b].pb(a);
  110. 		}
  111.  
  112. 		dfs(1, -1);
  113.  
  114. 		for (int i = 1; i <= n; i++) {
  115. 			cout << ans[i] << " ";
  116. 		}
  117. 		cout << "\n";
  118.  
  119. 	}
  120.  
  121. 	return 0;
  122. }
Success #stdin #stdout 0.02s 11648KB
comments (?)
stdin
copy 
3
4
100 101 102 103
1 2
1 3
1 4
4
2 2 2 2
1 2
2 3
3 4
5
43 525 524 12 289
1 2
1 3
3 4
4 5
stdout
copy 
192 2 8 2 
5 4 3 2 
1080 12 60 18 3
https://ideone.com/AXsjPn
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!