### rhezo's blog

By rhezo, history, 3 years ago, ,

Can anyone explain the centroid decomposition solution?

• +3

 » 3 years ago, # |   +5 Let's fix a current centroid (root).So, if path v - u with length k exists and path contains vertex root, we can split it to the two parts: from vertex v to the root and from root to vertex u. Note: vertexes v and u must be in different subtrees of root.Next, we process every subtreee of root from left to right (or another fixed order) by simple dfs(vertex, distance, edgecount), and collect map for each subtree (local), and one global map. Suppose now we are in vertex u, with distance D and edgeCount E, we should check, that global map contains k - D key, 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.
•  » » 3 years ago, # ^ |   0 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?
•  » » 4 weeks ago, # ^ |   0 I think it's enough to use an array of size k instead of a map if we are careful about reusing it. This way we can get O(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.
 » 3 years ago, # |   0 Where can we submit the problem?
•  » » 3 years ago, # ^ |   +11