fork(13) download
  1. #include<bits/stdc++.h>
  2. #define f first
  3. #define s second
  4. using namespace std;
  5.  
  6. int n;
  7. vector<int>ans;
  8. vector<bool>vis;
  9. vector<int>mas;
  10. vector<int>del;
  11. vector<int>koll;
  12. vector<vector<int>>edges;
  13.  
  14. int nod(int a, int b)
  15. {
  16. if (b == 0)
  17. return a;
  18. return nod(b, a % b);
  19. }
  20.  
  21. void dfs1(int v)
  22. {
  23. vis[v] = 1;
  24. for (auto u : edges[v])
  25. if (! vis[u])
  26. {
  27. ans[u] = nod(ans[v], mas[u]);
  28. dfs1(u);
  29. }
  30. }
  31.  
  32. void dfs2(int v, int dist)
  33. {
  34. vis[v] = 1;
  35. for (int i = 0; i < del.size(); i++)
  36. {
  37. koll[i] += (mas[v] % del[i] == 0);
  38. if (koll[i] >= dist)
  39. ans[v] = max(ans[v], del[i]);
  40. }
  41. for (auto u : edges[v])
  42. if (! vis[u])
  43. dfs2(u, dist + 1);
  44. for (int i = 0; i < del.size(); i++)
  45. koll[i] -= (mas[v] % del[i] == 0);
  46. }
  47.  
  48. signed main()
  49. {
  50. ios_base::sync_with_stdio(0);
  51. int n;
  52. cin>>n;
  53. ans.resize(n);
  54. vis.resize(n);
  55. mas.resize(n);
  56. edges.resize(n);
  57. for (int i = 0; i < n; i++)
  58. cin>>mas[i];
  59. for (int i = 0; i < n - 1; i++)
  60. {
  61. int a, b;
  62. cin>>a>>b;
  63. a--; b--;
  64. edges[a].push_back(b);
  65. edges[b].push_back(a);
  66. }
  67. int p = mas[0];
  68. mas[0] = 0;
  69. ans[0] = 0;
  70. dfs1(0);
  71. mas[0] = p;
  72. for (int i = 0; i < n; i++)
  73. vis[i] = 0;
  74. for (int i = 1; i*i <= mas[0]; i++)
  75. {
  76. if (mas[0] % i == 0)
  77. {
  78. del.push_back(i);
  79. del.push_back(mas[0] / i);
  80. if (i*i == mas[0])
  81. del.pop_back();
  82. }
  83. }
  84. sort(del.begin(), del.end());
  85. koll.resize(del.size());
  86. dfs2(0, 0);
  87. for (int i = 0; i < n; i++)
  88. cout<<ans[i]<<' ';
  89. return 0;
  90. }
Runtime error #stdin #stdout 0s 16072KB
stdin
Standard input is empty
stdout
Standard output is empty