Python Program for Centroid Decomposition

Centroid Decomposition is an advanced tree decomposition technique used to divide a tree into smaller balanced components.

It is extremely useful for solving path queries, distance problems, and optimization problems on trees.

1. Understanding the Problem

Given a tree, repeatedly break it into subtrees using centroids to efficiently process queries.

Goal: Decompose tree such that each subtree is at most half the size of the original

2. Method 1: Basic Concept

# A centroid is a node where removing it splits the tree
# into subtrees of size at most n/2

# Steps:
# 1. Find subtree sizes
# 2. Find centroid
# 3. Remove centroid
# 4. Recur on subtrees

The centroid ensures balanced decomposition of the tree.

3. Method 2: Compute Subtree Sizes

def dfs_size(u, parent):
    size[u] = 1
    for v in tree[u]:
        if v != parent and not removed[v]:
            dfs_size(v, u)
            size[u] += size[v]

This step calculates subtree sizes for centroid finding.

4. Method 3: Find Centroid

def find_centroid(u, parent, n):
    for v in tree[u]:
        if v != parent and not removed[v]:
            if size[v] > n // 2:
                return find_centroid(v, u, n)
    return u

Finds the centroid of the current subtree.

5. Method 4: Build Centroid Tree

def decompose(u, parent):
    dfs_size(u, -1)
    c = find_centroid(u, -1, size[u])
    parent_centroid[c] = parent
    removed[c] = True

    for v in tree[c]:
        if not removed[v]:
            decompose(v, c)

Recursively decomposes the tree and builds centroid tree.

6. Method 5: Query Example

# Example: minimum distance to a special node
# Traverse centroid tree upward
# Combine answers from subtrees efficiently

Queries are answered by leveraging centroid tree structure.

7. Algorithm

1. Compute subtree sizes using DFS.

2. Find centroid of current tree.

3. Mark centroid as removed.

4. Recursively decompose subtrees.

5. Build centroid tree.

8. Common Mistakes

1. Not updating removed nodes properly.

2. Incorrect subtree size calculation.

3. Infinite recursion due to missing checks.

4. Confusing centroid with tree center.

9. Applications

1. Distance queries in trees.

2. Path counting problems.

3. Dynamic tree queries.

4. Competitive programming problems.

Conclusion

Centroid Decomposition is a powerful divide-and-conquer technique for trees.

It enables solving complex tree problems efficiently by breaking them into smaller balanced subproblems.