fork download
copy 
  1. #include<bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. // #define int long long
  7. using ll = long long;
  8. using pii = pair<int, int>;
  9.  
  10. const int N  = 1e5 + 5;
  11. const int A  = 5e5 + 5;
  12. const int LG = 17;
  13.  
  14. int n, a[N];
  15. vector<pii> G[N];
  16. ll ans = 0;
  17.  
  18. vector<int> Gr[A], onNode;
  19. bool On[A];
  20. ll dist[N];
  21. int h[N];
  22.  
  23. /* ===================== LCA O(1) bằng Euler Tour + RMQ ===================== */
  24.  
  25. const int M = 2 * N;  
  26. const int LOGM = 20;
  27.  
  28. int E;
  29. int eulerArr[M];
  30. int depthArr[M];
  31. int firstPos[N];
  32. int lg2_[M + 1];
  33. int st[LOGM][M];
  34.  
  35. struct Event {
  36.     int u, p, type, w;
  37. };
  38.  
  39. inline void buildLCA(int root = 1) {
  40.     E = 0;
  41.     for (int i = 1; i <= n; ++i) firstPos[i] = -1;
  42.  
  43.     h[root] = 0;
  44.     dist[root] = 0;
  45.  
  46.     vector<Event> stck;
  47.     stck.reserve(2 * n);
  48.     stck.push_back({root, 0, 0, 0});
  49.  
  50.     while (!stck.empty()) {
  51.         Event e = stck.back(); stck.pop_back();
  52.         if (e.type == 0) {
  53.             if (e.p != 0) {
  54.                 h[e.u]    = h[e.p] + 1;
  55.                 dist[e.u] = dist[e.p] + e.w;
  56.             }
  57.             if (firstPos[e.u] == -1) firstPos[e.u] = E;
  58.             eulerArr[E] = e.u; depthArr[E] = h[e.u]; ++E;
  59.  
  60.             auto &adj = G[e.u];
  61.             for (int i = (int)adj.size() - 1; i >= 0; --i) {
  62.                 int v = adj[i].ft, w = adj[i].sc;
  63.                 if (v == e.p) continue;
  64.                 stck.push_back({e.u, e.p, 1, 0});   
  65.                 stck.push_back({v,   e.u, 0, w});  
  66.             }
  67.         } else {
  68.             eulerArr[E] = e.u; depthArr[E] = h[e.u]; ++E;
  69.         }
  70.     }
  71.  
  72.     lg2_[1] = 0;
  73.     for (int i = 2; i <= E; ++i) lg2_[i] = lg2_[i >> 1] + 1;
  74.  
  75.     for (int i = 0; i < E; ++i) st[0][i] = i;
  76.     for (int k = 1; (1 << k) <= E; ++k) {
  77.         int len = 1 << k, half = len >> 1;
  78.         for (int i = 0; i + len <= E; ++i) {
  79.             int x = st[k - 1][i];
  80.             int y = st[k - 1][i + half];
  81.             st[k][i] = (depthArr[x] < depthArr[y] ? x : y);
  82.         }
  83.     }
  84. }
  85.  
  86. inline int lca(int u, int v) {
  87.     int L = firstPos[u], R = firstPos[v];
  88.     if (L > R) swap(L, R);
  89.     int k  = lg2_[R - L + 1];
  90.     int i1 = st[k][L];
  91.     int i2 = st[k][R - (1 << k) + 1];
  92.     return (depthArr[i1] < depthArr[i2] ? eulerArr[i1] : eulerArr[i2]);
  93. }
  94. /* ========================================================================== */
  95.  
  96. inline ll getDist(int u, int v) {
  97.     int p = lca(u, v);
  98.     return dist[u] + dist[v] - 2LL * dist[p];
  99. }
  100.  
  101. namespace subfull {
  102. bool checksub() {
  103.     for (int i = 1; i <= n; i++) if (a[i] > 5000) return 0;
  104.     return 1;
  105. }
  106. void solve() {
  107.     for (int i = 1; i <= n; i++) {
  108.         for (int j = 1; j * j <= a[i]; j++) {
  109.             if (a[i] % j == 0) {
  110.                 if (!On[j]) On[j] = 1, onNode.push_back(j);
  111.                 Gr[j].push_back(i);
  112.  
  113.                 if (j * j != a[i]) {
  114.                     int t = a[i] / j;
  115.                     if (!On[t]) On[t] = 1, onNode.push_back(t);
  116.                     Gr[t].push_back(i);
  117.                 }
  118.             }
  119.         }
  120.     }
  121.  
  122.     buildLCA(1);
  123.  
  124.     for (int g: onNode) {
  125.         int A = Gr[g][0];
  126.         int B = A;
  127.         ll len = 0;
  128.         for (int b: Gr[g]) {
  129.             ll val = getDist(A, b);
  130.             if (val > len) {
  131.                 len = val;
  132.                 B = b;
  133.             }
  134.         }
  135.         swap(A, B);
  136.         len = 0;
  137.         for (int b: Gr[g]) {
  138.             ll val = getDist(A, b);
  139.             if (val > len) {
  140.                 len = val;
  141.                 B = b;
  142.             }
  143.         }
  144.         ans = max(ans, len * (ll)g);
  145.     }
  146.     cout << ans << "\n";
  147. }
  148. };
  149.  
  150. inline void prepare() {
  151.     for (int i = 1; i <= n; i++) G[i].clear();
  152.     for (int i: onNode) {
  153.         On[i] = 0;
  154.         Gr[i].clear();
  155.     }
  156.     onNode.clear();
  157. }
  158.  
  159. void solve() {
  160.     ans = 0;
  161.     for (int i = 1; i <= n; i++) cin >> a[i];
  162.     for (int i = 1; i < n; i++) {
  163.         int u, v, w; cin >> u >> v >> w;
  164.         G[u].push_back({v, w});
  165.         G[v].push_back({u, w});
  166.     }
  167.     subfull::solve();
  168.     prepare();
  169.     return;
  170. }
  171.  
  172. signed main() {
  173.     cin.tie(NULL)->sync_with_stdio(false); cout.tie(NULL);
  174.     if (ifstream("TREE.INP")) {
  175.         freopen("TREE.INP", "r", stdin);
  176.         freopen("TREE.OUT", "w", stdout);
  177.     }
  178.     while (cin >> n) {
  179.         if (!n) break;
  180.         solve();
  181.     }
  182.     return 0;
  183. }
  184.  
Success #stdin #stdout 0.01s 19896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mAVt52
language:
C++14 (gcc 8.3)
created:
18 days 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!