Guest User

Untitled

a guest
Jan 12th, 2019
1,195
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 200043;
  5.  
  6. vector<int> vs[N];
  7. vector<int> g[N];
  8. vector<int> g2[N];
  9. int a[N];
  10. int used[N];
  11. int d[N];
  12. int n;
  13. int cc = 0;
  14.  
  15. pair<int, int> bfs(int x, set<int>& used_vertices)
  16. {
  17. cc++;
  18. queue<int> q;
  19. q.push(x);
  20. d[x] = 1;
  21. used[x] = cc;
  22. pair<int, int> ans = make_pair(x, d[x]);
  23. while(!q.empty())
  24. {
  25. int k = q.front();
  26. used_vertices.insert(k);
  27. q.pop();
  28. ans = make_pair(k, d[k]);
  29. for(auto y : g2[k])
  30. {
  31. if(used[y] != cc)
  32. {
  33. used[y] = cc;
  34. d[y] = d[k] + 1;
  35. q.push(y);
  36. }
  37. }
  38. }
  39. return ans;
  40. }
  41.  
  42. int ans = 0;
  43.  
  44. void upd(int p)
  45. {
  46. if(vs[p].empty())
  47. return;
  48. for(auto x : vs[p])
  49. {
  50. g2[x].clear();
  51. for(auto y : g[x])
  52. if(a[y] % p == 0)
  53. g2[x].push_back(y);
  54. }
  55. set<int> used_vertices;
  56. for(auto x : vs[p])
  57. if(!used_vertices.count(x))
  58. {
  59. pair<int, int> z = bfs(x, used_vertices);
  60. pair<int, int> z2 = bfs(z.first, used_vertices);
  61. ans = max(ans, z2.second);
  62. }
  63. }
  64.  
  65. int main()
  66. {
  67. scanf("%d", &n);
  68. for(int i = 0; i < n; i++)
  69. {
  70. scanf("%d", &a[i]);
  71. int x = a[i];
  72. for(int j = 2; j * 1ll * j <= a[i]; j++)
  73. {
  74. if(a[i] % j == 0)
  75. {
  76. vs[j].push_back(i);
  77. while(a[i] % j == 0)
  78. {
  79. a[i] /= j;
  80. }
  81. }
  82. }
  83. if(a[i] > 1)
  84. {
  85. vs[a[i]].push_back(i);
  86. a[i] = 1;
  87. }
  88. a[i] = x;
  89. }
  90. for(int i = 0; i < n - 1; i++)
  91. {
  92. int x, y;
  93. scanf("%d %d", &x, &y);
  94. --x;
  95. --y;
  96. g[x].push_back(y);
  97. g[y].push_back(x);
  98. }
  99. for(int i = 2; i <= 200000; i++)
  100. upd(i);
  101. printf("%d\n", ans);
  102. }
RAW Paste Data