Centroid decomposition: nearest marked depot on a fixed tree

Centroid decomposition repeatedly removes a tree vertex whose removal leaves no component larger than half of the current component. Each original vertex records its distance to the centroids of the nested components that contain it. Marking a vertex improves the best marked distance stored at every centroid on that vertex's path. To query another vertex, combine its distance to each centroid with that centroid's best marked distance and take the minimum. Any route between a query vertex and a marked vertex crosses a centroid that separates their decomposition branches, so one of these combinations reaches the true tree distance. The example handles an unweighted static tree and marks only; it does not remove marks.

Operational case

The seven-depot road tree has branches through depots one and three. Before any mark, nearest marked distance from depot two is None. Marking depot four makes that distance three edges. Marking depot six then makes depot five one edge from a marked depot. A duplicate mark is a no-op. The road graph must contain exactly N-1 edges and be connected; a cycle would make the component traversal and distance records invalid. If dispatch later removes a road or adds a new depot, the centroid hierarchy is no longer the hierarchy of the current graph and must be rebuilt.

Working Python program

class MarkedDepotCentroids:
    def __init__(self, depot_count, roads):
        if depot_count < 1 or len(roads) != depot_count - 1:
            raise ValueError("roads must form a nonempty tree")
        self.adjacent = [[] for _ in range(depot_count)]
        for first, second in roads:
            if not (0 <= first < depot_count and 0 <= second < depot_count) or first == second:
                raise ValueError("invalid tree edge")
            self.adjacent[first].append(second)
            self.adjacent[second].append(first)
        seen = {0}
        pending = [0]
        while pending:
            for neighbor in self.adjacent[pending.pop()]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    pending.append(neighbor)
        if len(seen) != depot_count:
            raise ValueError("roads must connect every depot")
        self.blocked = [False] * depot_count
        self.paths = [[] for _ in range(depot_count)]
        self.best_marked = [float("inf")] * depot_count
        self.marked = set()
        self._decompose(0)

    def _decompose(self, start):
        parent = {start: -1}
        order = [start]
        for current in order:
            for neighbor in self.adjacent[current]:
                if neighbor != parent[current] and not self.blocked[neighbor]:
                    parent[neighbor] = current
                    order.append(neighbor)
        sizes = {node: 1 for node in order}
        for node in reversed(order):
            if parent[node] != -1:
                sizes[parent[node]] += sizes[node]
        total = len(order)
        centroid = min(order, key=lambda node: (
            max([total - sizes[node]] + [sizes[neighbor] for neighbor in self.adjacent[node]
                                          if not self.blocked[neighbor] and parent.get(neighbor) == node]), node))
        pending = [(centroid, -1, 0)]
        while pending:
            node, previous, distance = pending.pop()
            self.paths[node].append((centroid, distance))
            for neighbor in self.adjacent[node]:
                if neighbor != previous and not self.blocked[neighbor]:
                    pending.append((neighbor, node, distance + 1))
        self.blocked[centroid] = True
        for neighbor in self.adjacent[centroid]:
            if not self.blocked[neighbor]:
                self._decompose(neighbor)

    def mark(self, depot_id):
        if depot_id in self.marked:
            return False
        self.marked.add(depot_id)
        for centroid, distance in self.paths[depot_id]:
            self.best_marked[centroid] = min(self.best_marked[centroid], distance)
        return True

    def nearest_marked_distance(self, depot_id):
        result = min((distance + self.best_marked[centroid]
                      for centroid, distance in self.paths[depot_id]), default=float("inf"))
        return None if result == float("inf") else result


if __name__ == "__main__":
    network = MarkedDepotCentroids(7, [(0, 1), (1, 2), (1, 3), (3, 4), (3, 5), (5, 6)])
    print("before marking:", network.nearest_marked_distance(2))
    network.mark(4)
    print("from 2:", network.nearest_marked_distance(2))
    network.mark(6)
    print("from 5:", network.nearest_marked_distance(5))

Output

before marking: None
from 2: 3
from 5: 1

Time, space, and tradeoff

For N vertices, scanning and choosing a centroid at each level costs O(N log N) total in this implementation; distance-path storage is O(N log N). Once paths are built, a mark and a nearest-distance query inspect O(log N) centroid records. One mark only decreases best-distance values; supporting unmark would require per-centroid multisets or another reversible summary. Python lists and dictionaries increase actual memory. This data structure helps repeated marked-node distance queries over fixed topology, while heavy-light paths answer different path-aggregate questions and link-cut forests permit topology changes at higher implementation cost.

Common Mistakes

Do not use this mark-only summary for unmark without repairing every affected centroid record.
Do not apply it to a graph with cycles or changing tree edges.
Do not forget to include the marked vertex's entire centroid path.
Do not confuse nearest marked distance with the identity of a nearest depot.

Connected lessons

Compare its update and query contract with BK-trees: search incident labels within edit distance, Vantage-point trees: nearest depots by a metric radius, Two-level perfect hashing: exact static case membership, then complete the structure audit and decision quiz.