Centroid Decomposition Depth

Problem

Return the number of levels in the centroid decomposition tree of a tree.

Repeatedly find a centroid of the current component (smallest largest child part, ties by smallest index), remove it, and recurse on each remaining part; the depth is one plus the deepest child decomposition. edges is a list of [u, v] pairs. A single node has depth 1.

Hint

Every centroid step at least halves each remaining part, so the depth is logarithmic.

Test cases

case 1

in: [1,[]]

expected: 1

case 2

in: [2,[[0,1]]]

expected: 2

case 3

in: [4,[[0,1],[1,2],[2,3]]]

expected: 3

case 4

in: [7,[[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]]]

expected: 3

case 5

in: [6,[[0,1],[0,2],[0,3],[0,4],[0,5]]]

expected: 2

Starter codePython

def centroid_decomposition_depth(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor