Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Link-cut forests: change tree edges and sum a path

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A link-cut tree represents a forest through preferred paths held in auxiliary splay trees. Access changes which root-to-node path is preferred; make-root reverses a represented path so either endpoint can become its root. Each auxiliary node stores its own weight and a subtree total. After making the first endpoint root and accessing the second, the second auxiliary root summarizes the complete path, including both endpoints. This implementation also tracks the exact edges so a cut cannot silently remove a different connection. Links between already connected depots are rejected: cycles violate the forest contract. A disconnected path has no sum under this API.

Operational case

Depots D-19, D-26, and D-47 have weights 7, 11, and 13. Linking D-19 to D-26 and D-26 to D-47 makes their path total 31. Cut the second edge; connectivity from D-19 to D-47 becomes false. Add D-61 with weight 17, connect D-47 to D-61 and D-26 to D-61, and the new four-depot path totals 48. These are node weights. An edge-weight model needs a separate representation, often an extra node per edge. Trying to link D-19 and D-47 now must fail because they are already connected.

Working Python program

python
"""Link-cut forest with node-weight path sums and exact tree-edge cuts."""

from dataclasses import dataclass


@dataclass(eq=False)
class DepotNode:
    depot_id: str
    weight: int
    total: int = 0
    left: "DepotNode | None" = None
    right: "DepotNode | None" = None
    parent: "DepotNode | None" = None
    reverse_pending: bool = False

    def __post_init__(self):
        self.total = self.weight


def auxiliary_root(node: DepotNode) -> bool:
    return node.parent is None or (node.parent.left is not node and node.parent.right is not node)


def push(node: DepotNode) -> None:
    if node.reverse_pending:
        node.left, node.right = node.right, node.left
        for child in (node.left, node.right):
            if child:
                child.reverse_pending ^= True
        node.reverse_pending = False


def refresh(node: DepotNode) -> None:
    node.total = node.weight + (node.left.total if node.left else 0) + (node.right.total if node.right else 0)


def rotate(node: DepotNode) -> None:
    parent = node.parent
    grandparent = parent.parent
    if not auxiliary_root(parent):
        if grandparent.left is parent:
            grandparent.left = node
        else:
            grandparent.right = node
    node.parent = grandparent
    if parent.left is node:
        parent.left = node.right
        if node.right:
            node.right.parent = parent
        node.right = parent
    else:
        parent.right = node.left
        if node.left:
            node.left.parent = parent
        node.left = parent
    parent.parent = node
    refresh(parent)
    refresh(node)


def splay(node: DepotNode) -> None:
    ancestors = [node]
    current = node
    while not auxiliary_root(current):
        current = current.parent
        ancestors.append(current)
    for ancestor in reversed(ancestors):
        push(ancestor)
    while not auxiliary_root(node):
        parent = node.parent
        if not auxiliary_root(parent):
            grandparent = parent.parent
            if (grandparent.left is parent) == (parent.left is node):
                rotate(parent)
            else:
                rotate(node)
        rotate(node)


def access(node: DepotNode) -> None:
    previous = None
    current = node
    while current:
        splay(current)
        current.right = previous
        if previous:
            previous.parent = current
        refresh(current)
        previous = current
        current = current.parent
    splay(node)


def make_root(node: DepotNode) -> None:
    access(node)
    node.reverse_pending ^= True


def find_root(node: DepotNode) -> DepotNode:
    access(node)
    while True:
        push(node)
        if node.left is None:
            break
        node = node.left
    splay(node)
    return node


class DepotForest:
    def __init__(self, weights: dict[str, int]):
        if not weights:
            raise ValueError("at least one depot is required")
        self.nodes = {depot_id: DepotNode(depot_id, weight) for depot_id, weight in weights.items()}
        self.edges: set[frozenset[str]] = set()

    def connected(self, first_id: str, second_id: str) -> bool:
        return find_root(self.nodes[first_id]) is find_root(self.nodes[second_id])

    def link(self, first_id: str, second_id: str) -> None:
        first, second = self.nodes[first_id], self.nodes[second_id]
        if first is second or self.connected(first_id, second_id):
            raise ValueError("link would create a cycle")
        make_root(first)
        first.parent = second
        self.edges.add(frozenset((first_id, second_id)))

    def cut(self, first_id: str, second_id: str) -> None:
        edge = frozenset((first_id, second_id))
        if edge not in self.edges:
            raise KeyError("edge is not present")
        first, second = self.nodes[first_id], self.nodes[second_id]
        make_root(first)
        access(second)
        if second.left is not first or first.right is not None:
            raise AssertionError("direct edge representation was lost")
        second.left = None
        first.parent = None
        refresh(second)
        self.edges.remove(edge)

    def update(self, depot_id: str, weight: int) -> None:
        node = self.nodes[depot_id]
        access(node)
        node.weight = weight
        refresh(node)

    def path_sum(self, first_id: str, second_id: str) -> int:
        if not self.connected(first_id, second_id):
            raise ValueError("depots are disconnected")
        first, second = self.nodes[first_id], self.nodes[second_id]
        make_root(first)
        access(second)
        return second.total


forest = DepotForest({"D-19": 7, "D-26": 11, "D-47": 13, "D-61": 17})
forest.link("D-19", "D-26")
forest.link("D-26", "D-47")
print(forest.path_sum("D-19", "D-47"))
forest.cut("D-26", "D-47")
print(forest.connected("D-19", "D-47"))
forest.link("D-47", "D-61")
forest.link("D-26", "D-61")
print(forest.path_sum("D-19", "D-47"))

Output

Output
31
False
48

Time, space, and tradeoff

For N depots, node and direct-edge storage are O(N) in a forest. Standard splay-based link-cut operations have amortized O(log N) time; one particular operation can take longer, so this is not a worst-case latency guarantee. A path sum makes a constant number of those operations and has the same amortized bound. The splay implementation builds a temporary ancestor list during an access, which may use O(N) transient space in the worst case. A static tree with many path queries can use a precomputed path index instead. This example is single-threaded and does not maintain connectivity for arbitrary cyclic graphs.

Common Mistakes

  • Do not link nodes that already share a represented tree.
  • Do not cut an arbitrary path when the API requires an existing direct edge.
  • Do not report amortized logarithmic work as a per-request worst-case bound.
  • Do not treat node-weight sums as edge-weight sums without changing the model.

Connected lessons

Apply the invariant in the depot forest and notes project, then check the operations quiz.

Centroid decomposition: nearest marked depot on a fixed tree adds a distinct structure contract to compare.

data structures
range-query-structures
Storage details