fork download
copy 
  1. /*
  2. 	Em la may troi trong gio
  3. 	Anh la cay nhieu dan do
  4. */
  5.  
  6. #include "bits/stdc++.h"
  7. using namespace std;
  8.  
  9. #define ll long long
  10. #define endl '\n'
  11. #define fi first
  12. #define se second
  13. #define vall(a) (a).begin(), (a).end()
  14. #define sze(a) (int)a.size()
  15. #define pii pair<ll, ll>
  16.  
  17.  
  18. #define ep emplace_back
  19. #define pb push_back
  20. #define pf push_front
  21.  
  22.  
  23. const int mod = 1e9 + 7;
  24. const signed N = 1e5 + 5;
  25. const ll oo = 1e18;
  26.  
  27. int n, sz[N];
  28. vector<pii> adj[N];
  29. vector<int> uoc[N];
  30. bool del[N], check[N];
  31. ll ans = 0, cnt[N], boi[N], a[N];
  32.  
  33. int get_sz(int u, int p = 0) {
  34.     sz[u] = 1;
  35.     for (auto [v, c] : adj[u]) {
  36.         if(v == p || del[v]) continue;
  37.         sz[u] += get_sz(v ,u);
  38.     }
  39.     return sz[u];
  40. }
  41. int get_cen(int sigma, int u, int p = 0) {
  42.     for (auto[v, c] : adj[u]) if(v != p && !del[v] && sz[v] > (sigma >> 1)) return get_cen(sigma, v, u);
  43.     return u;
  44. }
  45.  
  46. stack<int> s;
  47. void calc(int u, int p, ll Gcd, ll depth, bool type) {
  48.     if (type) {
  49.         ans = max(ans, 1ll * (depth + boi[Gcd]) * Gcd);
  50.         for (int val : uoc[Gcd]) ans = max(ans, 1ll * (depth + cnt[val]) * val);
  51.     } else {
  52.         cnt[Gcd] = max(cnt[Gcd], depth);
  53.         if (!check[Gcd]) {
  54.             s.push(Gcd);
  55.             check[Gcd] = true;
  56.         }
  57.         for (int val : uoc[Gcd]) {
  58.             boi[val] = max(boi[val], depth);
  59.             if (!check[val]) {
  60.                 s.push(val);
  61.                 check[val] = true;
  62.             }
  63.         }
  64.     }
  65.     for (auto[v, c] : adj[u]) {
  66.         if (v == p || del[v]) continue;
  67.         calc(v, u, __gcd(Gcd, a[v]), depth + c, type);
  68.     }
  69. }
  70.  
  71. void decomp(int u = 1) {
  72.     u = get_cen(get_sz(u), u);
  73.     del[u] = true;
  74.     for (auto [v, c] : adj[u]) {
  75.         if (del[v]) continue;
  76.         calc(v, u, __gcd(a[u], a[v]), c, 1);
  77.         calc(v, u, __gcd(a[u], a[v]), c, 0);
  78.     }
  79.     while(!s.empty()) {
  80.         cnt[s.top()] = boi[s.top()] = 0;
  81.         check[s.top()] = false;
  82.         s.pop();
  83.     }
  84.     for (auto[v, c] : adj[u]) if (!del[v]) decomp(v);
  85. }
  86.  
  87. ll Max = 0;
  88.  
  89. void output() {
  90.     for(int x = 1; x <= Max; ++x) {
  91.         for (int i = 1; i * i <= x; ++i) {
  92.             if (x % i == 0) {
  93.                 uoc[x].pb(i);
  94.                 if (x / i != i) uoc[x].pb(x / i);
  95.             }
  96.         }
  97.     }
  98.     decomp();
  99.     cout << ans;
  100.     return;
  101. }
  102.  
  103. void input() {
  104. 	cin >> n;
  105.     for (int i = 1; i <= n; ++i) {
  106.         cin >> a[i];
  107.         Max = max(Max, a[i]);
  108.     }
  109.     for (int i = 1; i < n; ++i) {
  110.         int u, v, c;
  111.         cin >> u >> v >> c;
  112.         adj[u].ep(v, c);
  113.         adj[v].ep(u, c);
  114.     }
  115.  
  116.     output();
  117.     return;
  118. }
  119.  
  120. signed main () {
  121.     ios_base::sync_with_stdio(false);
  122.     cin.tie(nullptr); cout.tie(nullptr);
  123.  
  124.     input();
  125.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl;
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout #stderr 0.01s 10096KB
comments (?)
stdin
copy 
10  
12 15 10 18 20 25 30 35 40 50  
1 2 5  
1 3 10  
2 4 3  
2 5 6  
3 6 7  
3 7 8  
4 8 12  
5 9 15  
6 10 20
stdout
copy 
500
stderr
copy 
Time elapsed: 0.005159s
https://ideone.com/QEFXRO
language:
C++14 (gcc 8.3)
created:
20 hours 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!