fork(1) download
  1. #include <vector>
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <bitset>
  7. using namespace std;
  8. const int NMAX = 100004;
  9. const int VALMAX = 2e6;
  10. vector < int > Tree[NMAX];
  11. int value[NMAX], niv[NMAX] , answer[NMAX];
  12. bitset < VALMAX+6> viz;
  13. int prime[2*NMAX],pos[6+VALMAX];
  14. stack < int > St[2*NMAX];
  15. inline void Eratosthenes(){
  16. prime[++prime[0]] = 2;
  17. pos[2] = 1;
  18. for(int i = 3;i <= VALMAX;i += 2)
  19. if(!viz[i]){
  20. prime[++prime[0]] = i;
  21. pos[i] = prime[0];
  22. for(long long j = 1LL*i*i;j <= VALMAX; j += 2*i)
  23. viz[j] = 1;
  24. }
  25. }
  26. inline void DFS(const int node,const int father){
  27. vector < int > v;
  28. int d = 2,step = 1;
  29. int x = value[node];
  30. answer[node] = 0;
  31. while(d*d <= x){
  32. if(x%d==0){
  33. if(!St[pos[d]].empty()){
  34. int y = St[pos[d]].top();
  35. if(niv[y] > niv[answer[node]])
  36. answer[node] = y;
  37. }
  38. v.push_back(pos[d]);
  39. St[pos[d]].push(node);
  40. while(x%d==0)
  41. x /= d;
  42. }
  43. ++step;
  44. d = prime[step];
  45. }
  46. if(x > 1){
  47. if(!St[pos[x]].empty()){
  48. int y = St[pos[x]].top();
  49. if(niv[y] > niv[answer[node]])
  50. answer[node] = y;
  51. }
  52. v.push_back(pos[x]);
  53. St[pos[x]].push(node);
  54. }
  55. for(vector < int > ::iterator it = Tree[node].begin(); it != Tree[node].end(); ++it)
  56. if(*it!=father){
  57. niv[*it] = niv[node] + 1;
  58. DFS(*it,node);
  59. }
  60. for(vector < int > ::iterator it = v.begin(); it != v.end() ; ++it)
  61. St[*it].pop();
  62. v.clear();
  63. }
  64.  
  65. int main(){
  66. #ifndef ONLINE_JUDGE
  67. freopen("date.in","r",stdin);
  68. freopen("date.ok","w",stdout);
  69. #endif
  70. cin.sync_with_stdio(false);
  71. Eratosthenes();
  72. int n, m;
  73. cin >> n >> m;
  74. for(int i = 1;i <= n; ++i)
  75. cin >> value[i];
  76. for(int i = 1;i < n; ++i){
  77. int x, y;
  78. cin >> x >> y;
  79. Tree[x].push_back(y);
  80. Tree[y].push_back(x);
  81. }
  82. niv[1] = 1;
  83. DFS(1,-1);
  84. while(m--){
  85. int operation, x, y;
  86. cin >> operation >> x;
  87. if(operation == 1){
  88. if(answer[x] > 0)
  89. cout<<answer[x]<<"\n";
  90. else
  91. cout<<"-1\n";
  92. }
  93. else{
  94. cin >> y;
  95. value[x] = y;
  96. DFS(1,-1);
  97. }
  98. }
  99. return 0;
  100. }
Runtime error #stdin #stdout 0.17s 131904KB
stdin
Standard input is empty
stdout
Standard output is empty