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?

# | User | Rating |
---|---|---|

1 | tourist | 3372 |

2 | mnbvmar | 3345 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | Radewoosh | 3230 |

5 | scott_wu | 3189 |

6 | Benq | 3187 |

7 | LHiC | 3171 |

8 | Um_nik | 3155 |

9 | V--o_o--V | 3152 |

10 | Petr | 3139 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 172 |

3 | rng_58 | 159 |

4 | neal | 156 |

5 | Um_nik | 154 |

5 | tourist | 154 |

7 | PikMike | 152 |

8 | Ashishgup | 151 |

8 | Petr | 151 |

10 | 300iq | 150 |

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?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/14/2018 19:39:56 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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.

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.

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.