fork(12) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uQNFX3
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!