Блог пользователя n1e2m3

Please help me in HACKEREARTH Question: GCD ON TREE
Автор n1e2m3, история, 6 лет назад, По-английски

how to solve this problem?

problem link: https://www.hackerearth.com/problem/algorithm/gcd-on-tree-6c5cdfba/description/

how to apply centroid decomposition in this problem? or any other approach to solve this problem?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Some Possibly Helpful Hints

1) The answer for leaves is 0.

2) Using the technique here, we can find the maximum GCD of a pair in an array with square root complexity.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes,I have previously seen this algorithm. But I actually didn't get it how to apply this algorithm in this question. Can you describe more how to solve? Thanks in advance.

    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For node pair(u,v) if we only update ans[LCA(u,v)] instead of all nodes on the path(u,v), the problem can be solved using DSU on tree. For the extended case, to get ans[u], we take all the subtrees of u (let the root of the chosen subtree be v, which must be a son of u) and update ans[u] with all nodes in tree(v) and out of tree(v).

Sorry for my poor English; the solution is not tested but I think it'd work. Hope it helps.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I discussed the problem with my friends, we think that centroid decomposition will work too. Insert each subtree of the current centroid and we can get the answer of the centroid. Note that clearing array must be finished by undo all the operations have done, or the complexity would be wrong.

    → Ответить