Can anyone explain the centroid decomposition solution?

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

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

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

1 | adamant | 173 |

2 | awoo | 167 |

3 | SecondThread | 163 |

4 | BledDest | 162 |

4 | Um_nik | 162 |

6 | maroonrk | 161 |

6 | nor | 161 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

Can anyone explain the centroid decomposition solution?

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 17:19:50 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Let's fix a current centroid (

root).So, if path

v-uwith lengthkexists and path contains vertexroot, we can split it to the two parts: from vertexvto therootand fromrootto vertexu. Note: vertexesvandumust be in different subtrees ofroot.Next, we process every subtreee of

rootfrom left to right (or another fixed order) by simple dfs(vertex, distance, edgecount), and collect map<distance, edgeCount> for each subtree (local), and one global map. Suppose now we are in vertexu, with distanceDand edgeCountE, we should check, that global map containsk-Dkey, and update answer if can (answer=min(answer,E+global[k-D]), and update min in local map. After subtree processing, we merge local map to the global.Thanks. This works because for the original centroid we would have to process N vertices in our DFS. And after splitting the tree, in the subsequent DFSs the number of nodes to process gets half. And therefore the complexity would be O(NlogN) excluding the map log factor. Right?

I think it's enough to use an array of size

kinstead of a map if we are careful about reusing it. This way we can getO(N logN)without any hashing (if one wanted to use a hash map to remove the log factor from using a map). This is the official solution and it can be found here.Where can we submit the problem?

http://wcipeg.com/problem/ioi1112