n1e2m3's blog

Please help me in HACKEREARTH Question: GCD ON TREE
By n1e2m3, history, 6 years ago, In English

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?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply