fork download
  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
stdin
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
192 2 8 2 
5 4 3 2 
1080 12 60 18 3