#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/advanced-trees/centroid-decomposition-code

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/advanced-trees/centroid-decomposition-code

Repovive

Centroid Decomposition - Code - Advanced Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Centroid Decomposition - Code

Building the structure

Here's the decomposition:

function decompose(v, treeSize)
    centroid := findCentroid(v, treeSize)
    removed[centroid] := true

    // Process paths through centroid (problem-specific)
    processCentroid(centroid)

    for each neighbor u of centroid (not removed)
        childSize := subtreeSize[u]
        if childSize > treeSize / 2 then
            childSize := treeSize - subtreeSize[centroid]
        centroidParent[decompose(u, childSize)] := centroid

    return centroid

The $processCentroid$ function depends on the specific problem. It typically computes distances or counts for paths passing through the centroid.