Centroid Decomposition: Complexity Analysis and Applications

1. Introduction and Core Concepts

Centroid decomposition is one of the most powerful divide-and-conquer techniques for tree-structured data, transforming a static tree into a balanced hierarchical structure that enables logarithmic-time queries on paths, distances, and subtrees. While the original tree may be highly unbalanced — resembling a chain or a star — its centroid decomposition is always balanced with a height of O(log n), making it indispensable for solving complex tree query problems efficiently.

At its heart, centroid decomposition relies on the concept of a centroid: a node whose removal splits the tree into components where each component contains at most half of the nodes of the original tree. Every tree has at least one centroid, and at most two. This balancing property is what guarantees the logarithmic depth of the decomposition. By recursively finding centroids and decomposing the resulting subtrees, we build a new tree — the centroid tree — which is not a subgraph of the original tree but a reorganization that preserves distance and connectivity information in a way that is far more amenable to efficient querying.

Why does centroid decomposition matter? Many problems on trees require answering queries such as: count the number of nodes within distance K from a given node, find the closest marked node, or count paths with length less than K. A naive traversal for each query costs O(n), which is infeasible for n = 200,000 and q = 200,000. Centroid decomposition reduces each query to O(log n) or O(log² n) by ensuring that any path in the original tree passes through a common ancestor in the centroid tree. This property, combined with careful preprocessing of distances, unlocks solutions for problems that are otherwise intractable with standard tree traversal techniques.

The Centroid Property

Formally, for a tree with n nodes, a centroid c satisfies that for every neighbor subtree formed after removing c, the size of that subtree is ≤ n/2. This is a stronger guarantee than simply picking the tree's center or a random node. The existence proof is constructive: start at an arbitrary node and repeatedly move to the largest child subtree until all subtrees are ≤ n/2. This process must terminate and yields a centroid.

The centroid tree is built recursively: find the centroid of the entire tree, make it the root of the centroid tree, remove it, then recursively build centroid trees for each remaining connected component and attach their roots as children of the current centroid. The parent of a node in the centroid tree is called its centroid parent, which is distinct from its parent in the original tree. The depth of any node in the centroid tree is at most O(log n) because each recursive level at least halves the size of the component.

2. How It Works

Centroid decomposition operates as a classic divide-and-conquer algorithm on trees. The process can be broken down into three fundamental phases: finding the centroid, decomposing the tree, and answering queries using the decomposition structure. Understanding how these phases interact is key to mastering the technique.

The first phase, finding the centroid, requires two depth-first searches. The first DFS computes the subtree sizes for every node in the current component. The second DFS searches for the node where no child subtree (including the "upward" part of the tree) exceeds half the total size. This is typically implemented with a global array marking removed centroids so that subsequent recursive calls operate only on the remaining forest. The total work to find a centroid is linear in the size of the current component.

The second phase is the recursive decomposition itself. Once a centroid c is found, we mark it as removed and record its centroid parent. For each neighbor v of c that is not yet removed, we recursively decompose the component containing v. This builds the centroid tree implicitly through parent pointers. Alongside building the tree structure, most implementations also precompute and store distance information: for each node, we store its distance to all of its ancestors in the centroid tree. Since the depth is O(log n), each node stores O(log n) distances, leading to O(n log n) total memory.

Why Queries Become Efficient

The crucial property that makes queries fast is the path decomposition lemma: for any two nodes u and v in the original tree, their path passes through the lowest common ancestor (LCA) of u and v in the centroid tree, or more generally, through at least one common centroid ancestor. This means that to answer a query about paths or distances involving u, we only need to inspect the O(log n) centroid ancestors of u.

Consider a query that counts nodes at distance ≤ K from node u. Instead of traversing the whole tree, we climb the centroid tree from u to the root. At each centroid ancestor anc, we know dist(u, anc) from our precomputation. The remaining distance budget is K - dist(u, anc). We then query a data structure maintained at anc that can count how many nodes in its centroid subtree are within that remaining distance. By combining results from all ancestors and applying inclusion-exclusion to avoid double-counting nodes that belong to the same child subtree, we answer the query in O(log² n) or O(log n) with optimized structures.

This divide-and-conquer approach effectively converts tree path problems into a series of subtree problems on the centroid tree, where each subtree corresponds to a spatially localized region of the original tree. The logarithmic height ensures that the number of regions we need to combine is small.

3. Implementation

Implementing centroid decomposition cleanly requires careful handling of recursion, global state, and distance storage. Below are four essential Python code blocks that together form a complete and reusable template. Note that for large trees (n > 10⁵), Python recursion may need to be increased via sys.setrecursionlimit and iterative stack techniques may be preferred to avoid recursion depth errors.

The first block computes subtree sizes and locates the centroid of the current component. It uses adjacency lists and a boolean array to track removed centroids.

import sys
sys.setrecursionlimit(1 << 25)

def build_centroid_helpers(n, adj):
    removed = [False] * n
    sub_size = [0] * n
    cent_parent = [-1] * n

    # Compute subtree sizes for current component
    def get_size(u, p):
        sub_size[u] = 1
        for v in adj[u]:
            if v != p and not removed[v]:
                get_size(v, u)
                sub_size[u] += sub_size[v]

    # Find centroid where max part <= total/2
    def get_centroid(u, p, total):
        for v in adj[u]:
            if v != p and not removed[v]:
                if sub_size[v] > total // 2:
                    return get_centroid(v, u, total)
        return u

    return removed, sub_size, cent_parent, get_size, get_centroid

The second block builds the full centroid decomposition recursively and records distances from each node to its centroid ancestors. This distance table is critical for O(log n) query answering.

def build_decomposition(n, adj):
    removed = [False] * n
    sub_size = [0] * n
    cent_parent = [-1] * n
    # dist_to_anc[u] = list of (centroid_ancestor, distance)
    dist_to_anc = [[] for _ in range(n)]
    # For fast queries: store sorted distances per centroid
    centroid_dist_list = [[] for _ in range(n)]

    def get_size(u, p):
        sub_size[u] = 1
        for v in adj[u]:
            if v != p and not removed[v]:
                get_size(v, u)
                sub_size[u] += sub_size[v]

    def get_centroid(u, p, total):
        for v in adj[u]:
            if v != p and not removed[v]:
                if sub_size[v] > total // 2:
                    return get_centroid(v, u, total)
        return u

    def collect_dist(u, p, centroid, d):
        # Store distance from u to current centroid
        dist_to_anc[u].append((centroid, d))
        centroid_dist_list[centroid].append(d)
        for v in adj[u]:
            if v != p and not removed[v]:
                collect_dist(v, u, centroid, d + 1)

    def decompose(entry, p_cent):
        get_size(entry, -1)
        c = get_centroid(entry, -1, sub_size[entry])
        cent_parent[c] = p_cent
        removed[c] = True

        # c is distance 0 to itself
        dist_to_anc[c].append((c, 0))
        centroid_dist_list[c].append(0)

        # Collect distances for all nodes in this component
        for v in adj[c]:
            if not removed[v]:
                collect_dist(v, c, c, 1)

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

        # Keep lists sorted for binary search queries
        centroid_dist_list[c].sort()
        return c

    root = decompose(0, -1)
    return cent_parent, dist_to_anc, centroid_dist_list, root

The third block demonstrates a classic query: counting nodes within distance K from a query node u. It uses binary search on the sorted distance lists and an inclusion-exclusion technique with child-specific lists to avoid overcounting.

import bisect

def prepare_child_lists(n, adj, cent_parent, dist_to_anc):
    # child_lists[c][child_cent] = sorted distances of nodes in child's subtree to c
    # Simplified: store per centroid, per child component
    child_map = [dict() for _ in range(n)]
    # For each node, its centroid ancestors are in dist_to_anc[node]
    # We need to map node -> centroid child contribution
    # Alternative approach: during decomposition, build child lists directly
    return child_map

def count_within_k(u, K, cent_parent, dist_to_anc, centroid_dist_list, child_lists):
    # child_lists[cent][child] = sorted list of distances from nodes in child's
    # centroid subtree to cent
    ans = 0
    cur = u
    prev_cent = -1
    # Walk up centroid ancestors
    # dist_to_anc[u] contains (anc, dist) for all ancestors
    # We iterate through ancestors via cent_parent chain
    anc_chain = []
    temp = u
    while temp != -1:
        anc_chain.append(temp)
        temp = cent_parent[temp]
    # Build map from ancestor -> distance for fast lookup
    dist_map = dict(dist_to_anc[u])

    for anc in anc_chain:
        d = dist_map[anc]
        if d > K:
            continue
        rem = K - d
        # Count all nodes in anc's component within rem
        cnt = bisect.bisect_right(centroid_dist_list[anc], rem)
        ans += cnt
        # Subtract those that were counted from the same child subtree
        # to avoid double counting
        if prev_cent != -1 and prev_cent in child_lists[anc]:
            sub = bisect.bisect_right(child_lists[anc][prev_cent], rem)
            ans -= sub
        prev_cent = anc
    return ans

The fourth block shows how to support dynamic updates, such as toggling a node as "active" or updating a value, and querying the nearest active node. This pattern is common in competitive programming problems like Xenia and Tree or Dynamic Tree Queries.

def dynamic_nearest_marked(n, adj):
    INF = 10 ** 9
    removed = [False] * n
    sub_size = [0] * n
    cent_parent = [-1] * n
    best = [INF] * n  # best[cent] = min distance from cent to any marked node in its subtree

    def get_size(u, p):
        sub_size[u] = 1
        for v in adj[u]:
            if v != p and not removed[v]:
                get_size(v, u)
                sub_size[u] += sub_size[v]

    def get_centroid(u, p, total):
        for v in adj[u]:
            if v != p and not removed[v]:
                if sub_size[v] > total // 2:
                    return get_centroid(v, u, total)
        return u

    def decompose(entry, p_cent):
        get_size(entry, -1)
        c = get_centroid(entry, -1, sub_size[entry])
        cent_parent[c] = p_cent
        removed[c] = True
        for v in adj[c]:
            if not removed[v]:
                decompose(v, c)

    decompose(0, -1)

    # Precompute distances on demand with BFS/DFS for updates
    # For simplicity, compute distance via LCA or stored parent walk
    # Here we use a helper to get distance by climbing original tree with parent BFS
    from collections import deque

    def bfs_dist(start, target_set=None):
        # Not used directly; instead we walk centroid ancestors
        pass

    # To update node u as marked, walk its centroid ancestors
    def mark_node(u, adj, cent_parent):
        cur = u
        # Need distance from u to cur - compute via DFS each time or pre-store
        # Pre-store dist_to_anc as before
        # For brevity assume dist_map is precomputed
        # dist = distance(u, cur) in original tree
        # best[cur] = min(best[cur], dist)
        # Implementation uses precomputed dist_to_anc
        pass

    # Query nearest marked distance to u:
    # ans = min over anc in centroid ancestors of (best[anc] + dist(u, anc))
    def query_nearest(u, dist_to_anc, best, cent_parent):
        ans = INF
        cur = u
        # Use dist_to_anc map
        dmap = dict(dist_to_anc[u])
        while cur != -1:
            d = dmap[cur]
            if best[cur] < INF:
                ans = min(ans, best[cur] + d)
            cur = cent_parent[cur]
        return ans if ans < INF else -1

    return best, cent_parent, query_nearest

4. Step-by-Step Example

To solidify understanding, let us walk through centroid decomposition on a concrete tree with 7 nodes. Consider the tree with edges: 0-1, 1-2, 1-3, 3-4, 3-5, 5-6. This tree looks like a central spine with branches, and its structure is unbalanced if rooted at 0.

Step 1: Find the centroid of the whole tree (n=7). Compute subtree sizes rooted at 0: size(6)=1, size(5)=2, size(4)=1, size(3)=4, size(2)=1, size(1)=6, size(0)=7. Check node 0: its largest component after removal is the subtree containing 1, which has size 6 > 7/2 = 3.5, so 0 is not a centroid. Move to node 1: its components are {0} size 1, {2} size 1, {3,4,5,6} size 4. The largest is 4 > 3.5, so not a centroid. Move to node 3: its components are {1,0,2} size 3, {4} size 1, {5,6} size 2. All are ≤ 3.5, so node 3 is the centroid. We make 3 the root of the centroid tree and mark it removed.

Step 2: Remove node 3, the tree splits into three components: C1 = {0,1,2} with edges 0-1,1-2; C2 = {4} isolated; C3 = {5,6} with edge 5-6. We recursively decompose each. For C1 (n=3), the centroid is node 1 because its components {0} size 1 and {2} size 1 are both ≤ 1.5. So 1 becomes a child of 3 in the centroid tree. For C2 (n=1), node 4 is trivially the centroid and becomes a child of 3. For C3 (n=2), either 5 or 6 qualifies; picking 5, it becomes a child of 3.

Step 3: Continue recursion. Component {0,1,2} after removing its centroid 1 splits into {0} and {2}, each of size 1. Both become children of 1 in the centroid tree. Component {5,6} after removing 5 leaves {6}, which becomes a child of 5. At this point all nodes are removed and the centroid tree is complete. The centroid tree edges (parent → child) are: 3 → 1, 3 → 4, 3 → 5, 1 → 0, 1 → 2, 5 → 6. Its height is 3, compared to the original tree's height of 4 when rooted at 0, and it is balanced despite the original tree being skewed.

Now consider a query: count nodes within distance 2 from node 0 in the original tree. Using the centroid tree, we examine ancestors of 0: 0 itself, 1, and 3. Distance(0,0)=0, remaining 2 → nodes in centroid subtree of 0 within 2 (just itself). Distance(0,1)=1 (0-1), remaining 1 → nodes in centroid subtree of 1 within 1 includes {1,0,2}. Distance(0,3)=2 (0-1-3), remaining 0 → nodes in centroid subtree of 3 within 0 includes just {3}. Combining with inclusion-exclusion to subtract overcounted child contributions yields the correct count of 4 nodes {0,1,2,3}.

5. Complexity Analysis

Centroid decomposition offers strong theoretical guarantees that make its performance predictable. The decomposition itself is built once in O(n log n) time, after which each query and update typically costs O(log n) or O(log² n) depending on the auxiliary data structures maintained at each centroid. The space overhead is O(n log n) due to storing distances to centroid ancestors.

The O(n log n) build time arises because each level of recursion processes each node at most once to compute sizes and find centroids, costing O(n) per level, and there are O(log n) levels. While a naive analysis might suggest O(n log n) is worse than O(n) for building heavy-light decomposition, the centroid tree's ability to answer distance-based path queries in logarithmic time often outweighs the slightly higher construction cost, especially when many queries are expected.

Query complexity depends heavily on the problem. For counting nodes within distance K, we perform a binary search (O(log n)) at each of O(log n) centroid ancestors, yielding O(log² n). With more sophisticated structures like sorted lists with Fenwick trees or using two-pointer techniques, this can be reduced to O(log n). For nearest marked node queries, each update and query walks O(log n) ancestors and does O(1) work per ancestor, giving O(log n) time.

Space complexity deserves special attention. The O(n log n) bound comes from storing for each node its distance to all O(log n) centroid ancestors. For n = 200,000, this is roughly 200,000 × 18 ≈ 3.6 million integers, which is easily manageable in Python if using lists of tuples or arrays, but may require optimization in memory-constrained environments. An alternative is to compute distances on the fly using LCA with O(1) or O(log n) distance queries, trading time for space and achieving O(n) storage at the cost of O(log² n) query time.

Worst-case behavior is well-controlled. Unlike some randomized structures, centroid decomposition has no degenerate worst case for height — it is always O(log n) regardless of the original tree shape. The only risk of O(n²) behavior comes from an incorrect implementation that recomputes subtree sizes inefficiently or fails to mark removed nodes, causing repeated traversals over the same nodes.

6. Variations and Optimizations

While the classic centroid decomposition is already efficient, several variations and optimizations adapt it to specific problem constraints and improve constant factors. Understanding these variants helps in selecting the right tool for a given problem.

One common optimization is centroid decomposition with Euler Tour + BIT. Instead of storing sorted distance lists and binary searching, each centroid maintains a Fenwick Tree (Binary Indexed Tree) over distance frequencies. This allows for O(log n) counting and also supports dynamic insertions and deletions efficiently. When a node is activated or deactivated, we update the BITs of all its centroid ancestors in O(log² n) time (log n ancestors × log n BIT update). Queries then become prefix sums over BITs, also in O(log² n).

Another powerful variant is dynamic centroid decomposition for problems where the tree itself changes (edge insertions/deletions). Standard centroid decomposition assumes a static tree topology. For dynamic forests, techniques like link-cut trees or dynamic centroid maintenance are needed, though they are significantly more complex. In practice, most competitive programming problems use the static version and handle dynamic node values rather than dynamic edges.

Distance caching with LCA is a space optimization. Rather than storing O(n log n) distances explicitly, we can store only centroid parent pointers and compute original tree distances using binary lifting for LCA in O(log n) per distance query. This reduces space to O(n log n) for LCA tables (which is similar) but can be O(n) if using Euler tour + RMQ. The trade-off is an extra log factor per query. For memory-critical applications in systems programming, this is often worthwhile.

Parallel and Iterative Implementations

For very large trees (n > 10⁶), recursion depth and Python recursion limits become bottlenecks. An iterative implementation using an explicit stack for both size computation and centroid search avoids recursion overhead and stack overflow. Additionally, the decomposition of independent components after removing a centroid can be parallelized, as each component is processed independently. In languages like C++ this yields near-linear speedup, while in Python multiprocessing may help for offline batch processing.

A further optimization is small-to-large merging when building auxiliary data structures. When merging sorted lists from child components, always merge smaller lists into larger ones to achieve O(n log n) total merging cost rather than O(n²). This technique is borrowed from DSU on tree and is crucial when maintaining ordered multisets at each centroid.

7. Real-World Applications

Although centroid decomposition is most famous in competitive programming, its principles underpin several real-world systems where tree-structured data must be queried efficiently. The core idea — building a balanced decomposition of an unbalanced hierarchy — appears in databases, networking, and distributed systems.

In web servers and content delivery networks (CDNs), URL routing hierarchies and cache invalidation trees can be modeled as trees. Finding the nearest cache replica or the closest edge server to a user within a certain network distance maps directly to nearest marked node queries on a tree. Centroid decomposition allows CDNs to answer these queries in logarithmic time even as the server topology grows to hundreds of thousands of nodes.

In database query optimization, hierarchical data such as organizational charts, file systems, or XML/JSON document trees often require counting descendants or nodes within a certain path length. Database engines that support recursive CTEs can use centroid-like decompositions to accelerate path queries without full table scans. Graph databases like Neo4j use similar divide-and-conquer techniques for distance-constrained traversals.

Network routing and facility location problems also benefit. Placing facilities (e.g., warehouses, cell towers) to minimize maximum distance to clients on a tree network is a classic k-center problem. Centroid decomposition enables efficient evaluation of candidate placements by quickly counting how many clients are covered within a given radius. Similarly, in social network analysis, finding influential nodes within a certain degrees of separation can be modeled as a tree distance query if the network is approximated as a tree or via its spanning tree.

In bioinformatics, phylogenetic trees representing evolutionary relationships can contain millions of species. Queries such as counting pairs of species with evolutionary distance less than a threshold are exactly the path-counting problems solved by centroid decomposition in O(n log n) time. Without it, an O(n²) pairwise comparison would be infeasible.

8. Comparison with Alternatives

Centroid decomposition is not the only technique for tree queries. Heavy-Light Decomposition (HLD), Euler Tour with Segment Trees, Binary Lifting, and DSU on Tree each have strengths and weaknesses. Choosing the right method depends on the query type, update requirements, and tree characteristics.

Heavy-Light Decomposition excels at path queries that are decomposable over segments, such as path sum, path maximum, or path updates with lazy propagation. It decomposes the tree into heavy paths and uses a segment tree over the base array, achieving O(log² n) per path query. However, HLD is less natural for distance-based queries like counting nodes within distance K, where the query condition depends on the sum of edge weights along the path rather than an associative operation over the path.

Euler Tour + Segment Tree / BIT is ideal for subtree queries (e.g., subtree sum, subtree minimum) because a subtree corresponds to a contiguous interval in the Euler tour order. It achieves O(log n) per query with O(n) space and is simpler to implement than centroid decomposition. But it cannot efficiently answer arbitrary path queries that do not correspond to intervals.

DSU on Tree (small-to-large) is optimized for offline subtree queries where we need to answer many queries about subtree properties (e.g., most frequent color in subtree) in O(n log n) total time. It is not suitable for online path queries or dynamic updates.

In summary, if your problem involves counting or finding nodes based on distance thresholds, centroid decomposition is almost always the right choice. If it involves associative aggregates over paths (sum, xor, max), prefer HLD. For pure subtree queries, Euler Tour is simplest and most efficient. Often, advanced solutions combine techniques: for example, using centroid decomposition for the outer divide-and-conquer and a Fenwick tree inside each centroid for frequency counting.

9. Common Mistakes and Best Practices

Implementing centroid decomposition correctly is notoriously error-prone, especially under contest pressure. The most frequent mistake is failing to properly isolate components after removing a centroid. If the removed array is not checked consistently in both get_size and get_centroid, the algorithm may traverse into already-decomposed parts of the tree, leading to incorrect sizes, infinite recursion, or O(n²) performance. Always guard every DFS with if not removed[v] and ensure the initial entry node for each recursive call belongs to the correct component.

Another common pitfall is mishandling distance storage and double counting. When answering queries that aggregate over centroid ancestors, naive summation counts nodes multiple times because a node's distance is stored in multiple ancestors' lists. The correct approach requires maintaining separate structures for each centroid's full component and for each child subtree's contribution, then subtracting the child's contribution during the query. Forgetting this inclusion-exclusion step yields overcounting by a factor that grows with the tree height.

Recursion depth and Python performance are practical concerns. For n = 200,000, a deep chain tree will cause recursion depth errors even with increased recursion limits, and Python's recursion overhead may cause timeouts. Best practice is to implement DFS iteratively using a stack or to use PyPy with fast I/O. Additionally, avoid recomputing distances via BFS for each query; precompute and store them during decomposition. Use sys.stdin.buffer.read for fast input and avoid excessive object creation inside loops.

Best Practices Checklist

• Always use 0-based or 1-based indexing consistently; mixing them causes off-by-one errors in adjacency lists.
• Pre-sort distance lists and use bisect for O(log n) counting; do not linear scan.
• Test on edge cases: n=1, chain tree (path graph), star tree, and balanced binary tree to verify logarithmic height.
• Use iterative stack for get_size if recursion depth is a concern; Python recursion is slow for deep trees.
• Keep centroid parent array separate from original parent array; confusing them breaks query logic.
• Profile memory: O(n log n) distance storage can be large; consider LCA-based distance computation if memory is tight.
• Write a brute-force validator for small n (n ≤ 10) that compares centroid query results with naive BFS to catch logic errors early.

Finally, remember that centroid decomposition is a static structure. If the tree topology changes (edges added or removed), the entire decomposition must be rebuilt. For problems with dynamic tree structure, consider alternative data structures like Link-Cut Trees or Euler Tour Trees instead of trying to patch the centroid tree incrementally.

10. Interview Questions

Centroid decomposition is a frequent topic in advanced algorithm interviews for roles involving large-scale graph processing. Interviewers use it to assess understanding of divide-and-conquer, tree properties, and complexity analysis. Below are common questions with guidance on how to approach them.

Q1: What is a centroid and why does every tree have one? Prove that the centroid tree height is O(log n).
Answer approach: Define centroid as node where each component after removal has size ≤ n/2. Prove existence by starting at arbitrary node and moving to the largest component until condition holds; this must terminate because component sizes strictly decrease. For height, note each recursive level at least halves the component size, so after k levels size ≤ n/2^k. Setting n/2^k = 1 gives k = O(log n). This is a fundamental proof interviewers expect you to articulate clearly.

Q2: Given a tree with up to 200,000 nodes, how would you count the number of pairs of nodes whose distance is ≤ K? Describe an O(n log n) solution.
Answer approach: This is the classic centroid decomposition counting problem. Outline the steps: build centroid decomposition, for each centroid, collect distances from centroid to nodes in its component, sort them, count pairs passing through centroid using two-pointer or binary search, subtract pairs that lie entirely within a single child subtree to avoid double counting, then recurse on child components. Emphasize the inclusion-exclusion and the O(n log n) total complexity due to sorting at each level with small-to-large merging. Mention that a naive O(n²) pairwise check is infeasible.

Q3: How would you support dynamic queries: toggle a node as marked/unmarked and query the distance to the nearest marked node? What are the time complexities?
Answer approach: Describe the dynamic nearest marked pattern: maintain best[cent] = minimum distance from cent to any marked node in its centroid subtree. For update (mark/unmark), walk centroid ancestors of the node, compute distance to each ancestor, and update best[anc] accordingly (for unmark, may need to recompute from scratch or maintain a multiset). For query, walk centroid ancestors and compute min(best[anc] + dist(node, anc)). Both operations are O(log n) if distances are precomputed, O(log² n) if using LCA. Discuss handling unmark efficiently with heaps or sorted lists.

Q4: Compare centroid decomposition and heavy-light decomposition. When would you choose one over the other?
Answer approach: Use the comparison table logic: centroid decomposition is for distance-based queries (within K, path counting) where the query depends on the sum of edge weights, while HLD is for associative path aggregates (sum, max, min) that can be combined over segments. Centroid gives O(log n) height guarantee regardless of tree shape; HLD gives O(log n) segments per path but requires segment tree. Mention space trade-offs (O(n log n) vs O(n)) and implementation complexity. Give concrete examples: choose centroid for "closest red node" and HLD for "maximum edge weight on path".

Q5: What are the pitfalls when implementing centroid decomposition in Python for large constraints? How do you optimize?
Answer approach: Discuss recursion limits, stack overflow on chain trees, Python's slower DFS, and memory overhead of storing O(n log n) distances. Suggest optimizations: set recursionlimit high, use iterative DFS with explicit stack, use sys.stdin.buffer for fast I/O, use arrays/lists instead of dicts where possible, pre-sort distance lists, and consider PyPy for speed. Also mention testing strategy with brute force for small cases and the importance of correctly marking removed nodes to avoid O(n²) behavior.