#define log std::__lg
#define ctz __builtin_ctz 
 
// Rooted tree
struct arborescence {
    std::vector<std::vector<int>> children;
    int root;
};
 
arborescence shallowest_decomposition_tree(std::vector<std::vector<int>> &graph, int root=0) {
    int n = (int)graph.size();
    std::vector<std::vector<int>> decomposition_tree(n), stacks(log(n) + 1);
    
    auto extract_chain = [&](int labels, int u) {
        while (labels) {
            int label = log(labels);
            labels ^= 1 << label;
            int v = stacks[label].back(); stacks[label].pop_back();
            decomposition_tree[u].push_back(v);
            u = v;
        }
    };
    std::vector<int> forbidden(n, -1);
    auto dfs = [&](int u, int p, auto&& self) -> void {
        int forbidden_once = 0, forbidden_twice = 0;
        for (auto v : graph[u]) {
            if (v != p) {
                self(v, u, self);
                forbidden_twice |= forbidden_once & (forbidden[v] + 1);
                forbidden_once |= forbidden[v] + 1;
            }
        }
        forbidden[u] = forbidden_once | ((1 << log(2*forbidden_twice  + 1)) - 1);
        int label_u = ctz(forbidden[u] + 1);
        stacks[label_u].push_back(u);
        for (int i = (int)graph[u].size() - 1; i >= 0; --i) {
            int v = graph[u][i];
            extract_chain((forbidden[v] + 1) & ((1 << label_u) - 1), u);
        }
    };
    dfs(root, -1, dfs);
    int max_label = log(forbidden[root] + 1);
    int decomposition_root = stacks[max_label].back(); stacks[max_label].pop_back();
    extract_chain((forbidden[root] + 1) & ((1 << max_label) - 1), decomposition_root);
    return {std::move(decomposition_tree), decomposition_root};
}

def ctz(x): # Count trailing zeroes
    return (x & -x).bit_length() - 1
 
def shallowest_decomposition_tree(graph, root=0):
    n = len(graph)
    forbidden = [-1] * n
    decomposition_tree = [[] for _ in range(n)]
    stacks = [[] for _ in range(n.bit_length())]
    def extract_chain(labels, u):
        while labels:
            label = labels.bit_length() - 1
            labels ^= 2**label
            v = stacks[label].pop()
            decomposition_tree[u].append(v)
            u = v
    def dfs(u, p):
        forbidden_once = forbidden_twice = 0
        for v in graph[u]:
            if v != p: 
              dfs(v, u)
              forbidden_twice  |= forbidden_once & (forbidden[v] + 1)
              forbidden_once  |= forbidden[v] + 1
        forbidden[u] = forbidden_once | (2**forbidden_twice.bit_length() - 1)    
        label_u = ctz(forbidden[u] + 1)
        stacks[label_u].append(u)
        for v in reversed(graph[u]): 
            extract_chain((forbidden[v] + 1) & (2**label_u - 1), u)
    dfs(root, -1)
    max_label = (forbidden[root] + 1).bit_length() - 1
    decomposition_root = stacks[max_label].pop()
    extract_chain((forbidden[root] + 1) & (2**max_label - 1), decomposition_root)
    return decomposition_tree, decomposition_root

Since doing deep recursion in Python is generally a really bad idea. I've also implemented a slightly less nice looking version without recursion. This is what you should actually use in practice.

def ctz(x): # Count trailing zeroes
    return (x & -x).bit_length() - 1
 
def shallowest_decomposition_tree(graph, root=0):
    n = len(graph)
    forbidden = [0] * n
    decomposition_tree = [[] for _ in range(n)]
    stacks = [[] for _ in range(n.bit_length())]
    def extract_chain(labels, u):
        while labels:
            label = labels.bit_length() - 1
            labels ^= 2**label
            v = stacks[label].pop()
            decomposition_tree[u].append(v)
            u = v
    dfs = [root]
    while dfs:
        u = dfs.pop()
        if u >= 0:
            forbidden[u] = -1
            dfs.append(~u)
            for v in graph[u]:
                if not forbidden[v]:
                    dfs.append(v)
        else:
            u = ~u
            forbidden_once = forbidden_twice = 0
            for v in graph[u]:
                forbidden_twice  |= forbidden_once & (forbidden[v] + 1)
                forbidden_once  |= forbidden[v] + 1
            forbidden[u] = forbidden_once | (2**forbidden_twice.bit_length() - 1)    
            label_u = ctz(forbidden[u] + 1)
            stacks[label_u].append(u)
            for v in graph[u]: 
                extract_chain((forbidden[v] + 1) & (2**label_u - 1), u)
    max_label = (forbidden[root] + 1).bit_length() - 1
    decomposition_root = stacks[max_label].pop()
    extract_chain((forbidden[root] + 1) & (2**max_label - 1), decomposition_root)
    return decomposition_tree, decomposition_root

#define remover(vec, v) vec.erase(find(vec.begin(), vec.end(), v))
 
// Rooted tree
struct arborescence {
    std::vector<std::vector<int>> children;
    int root;
};
 
arborescence centroid_decomposition_tree(std::vector<std::vector<int>> graph) {
    int n = graph.size();
    std::vector<int> subtree_size(n);
    auto dfs = [&](int u, auto&& self) -> int {
        for (auto v : graph[u]) {
            remover(graph[v], u);
            subtree_size[u] += self(v, self);
        }
        return ++subtree_size[u];
    };
    dfs(0, dfs);
    
    std::vector<std::vector<int>> decomposition_tree(n);
    auto centroid_reroot = [&](int u, auto&& self) -> int {
        int N = subtree_size[u];
        for (bool found = 0; !found;) {
            found = 1;
            for (auto v : graph[u]) {
                if (subtree_size[v] > N / 2) {
                    found = 0;
                    subtree_size[u] = N - subtree_size[v];
                    remover(graph[u], v);
                    graph[v].push_back(u);
                    u = v;
                    break;
                }
            }
        }
        for (auto v : graph[u]) {
            decomposition_tree[u].push_back(self(v, self));
        }
        return u;
    };
    int decomposition_root = centroid_reroot(0, centroid_reroot);
    return {std::move(decomposition_tree), decomposition_root};
}

def centroid_decomposition_tree(graph):
    n = len(graph)
    graph = [c[:] for c in graph] # copy
    bfs = [0]
    for node in bfs:
        bfs += graph[node]
        for nei in graph[node]:
            graph[nei].remove(node)
    size = [0] * n
    for node in reversed(bfs):
        size[node] = 1 + sum(size[child] for child in graph[node])
    decomposition_tree = [[] for _ in range(n)]
    def centroid_reroot(u):
        N = size[u]
        while True:
            for v in graph[u]:
                if size[v] > N // 2:
                    size[u] = N - size[v]
                    graph[u].remove(v)
                    graph[v].append(u)
                    u = v
                    break
            else: # u is the centroid
                decomposition_tree[u] = [centroid_reroot(v) for v in graph[u]]
                return u
    decomposition_root = centroid_reroot(0)
    return decomposition_tree, decomposition_root

Suppose you are given a tree, where there is a treasure hidden at some node on this tree. Initially, you do not know where the treasure is hidden, but you are allowed to make guesses of where the treasure is hidden. If you guess that the treasure is at some node $$$u$$$, then

• if the treasure is at node $$$u$$$, then you have found the treasure and you are done.
• if the treasure is not at node $$$u$$$, then you will be told the direction of the treasure, i.e. which neighbour of u is in the direction of the treasure.

The goal is to find the treasure using the fewest possible number of guesses (in the worst case).

This tree is an example where centroid decomposition has depth $$$4$$$, but there exists a decomposition tree with depth $$$3$$$.

The red node marks the centroid of the tree. Note that the centroid guessing strategy requires $$$4$$$ guesses in the worst case to find the treasure. However, by guessing the blue node first, you only need 3 guesses to find the treasure.

Construct a tree of $$$n$$$ nodes consisting of several stars, where $$$n$$$ is some power of two minus one. Make the first star out of $$$(n + 1)/2$$$ nodes, the second star out of $$$(n + 1)/4$$$ nodes, the 3rd star out of $$$(n + 1)/8$$$ nodes, etc... Finally, the smallest star should have exactly $$$2$$$ nodes in it. There will now be one node left over. Connect that node to the centers of all of the stars.

Here is an example of the starry tree for $$$n=15$$$. It consists of $$$3$$$ stars and a top node connecting the centers of all of the stars.

Note that the centroid decomposition will split the stars in the order of largest star to smallest star. So the centroid decomposition tree has depth $$$O(\log n)$$$. But if you first split at the top node, you will get a decomposition of depth $$$3$$$. So this graph is an example of where the centroid decomposition can be beaten by a factor of $$$O(\log(n))$$$.

To create this tree, start with a single node. Then from this starting node, build out paths of odd lengths $$$(3,5,7, ...)$$$.

Here is an example with 4 paths going out from the starting node (which is placed at the top).

Note that the center of this graph is the right most child of the starting node. This results in a really unbalanced decomposition tree with a depth of $$$O(\sqrt{n})$$$, which is far from optimal. In comparison, the centroid decomposition tree has a depth of $$$O(\log{n})$$$.

Given a tree. A labeling of the nodes in the tree is called valid iff

1. Each node is labeled by a non-negative integer.

2. If two nodes $$$u$$$ and $$$v$$$ have the same label $$$L = \text{label}(u) = \text{label}(v)$$$, then there must exist some node $$$w$$$ on the path between $$$u$$$ and $$$v$$$ such that $$$\text{label}(w) > L$$$.

The goal is to as few distinct labels as possible.

Note that the version of this problem up on Codeforces (321C - Ciel the Commander) simply requires the usage of at most $$$26$$$ different labeles, making it so centroid decomposition is sufficient to solve the problem. But the goal for this blog is to instead solve this labeling problem optimally, using as few distinct labels as possible.

Start by picking some arbitrary node as the root. Then label the nodes bottom up, starting from the leaves. Label each node greedily by picking the smallest possible allowed label. I.e. give $$$u$$$ the smallest possible label such that there is no contradiction with the labels of the decedants of $$$u$$$.

Remark: The greedy labeling does depend on the choice of the root, so the choice of the root is not completely arbitrary. However, as we will see in Section 3.2, the number of distinct labels used is independent of the choice of the root. So the choice of the root does not matter in the end.

Recall the DP-algorithm used to compute forbidden(u) in the case of greedy labeling. It computes which labels are forbidden for $$$u$$$ based on the values of forbidden(v) + 1 over all children $$$v$$$ of $$$u$$$. Note that this DP-algorithm can be modified to compute forbidden(u) for any labeling (and not just the greedy labeling). To do this, instead of always adding + 1, we need to add some other number $$$b_v \geq 1$$$. The value of $$$b_v$$$ depends only on the label of $$$v$$$ and the value of forbidden(v).

Here is a generalized DP-algorithm that given a root and a labeling computes forbidden(u) for all nodes $$$u$$$:

def compute_b(label_v, forbidden_v):
    assert 2**label_v & forbidden_v == 0
    b_v = ((forbidden_v | 2**label_v) & ~(2**label_v - 1)) - forbidden_v
    assert b_v >= 1
    # Note: if v was labeled greedily, then b_v will be 1
    # A non-greedy choice of labeling v will make b_v > 1.
    return b_v

forbidden = [0] * n
def dfs(u, p):
    forbidden_once = forbidden_twice = 0
    for v in graph[u]:
        if v != p:
            dfs(v, u)
            forbidden_by_v = forbidden[v] + compute_b(label[v], forbidden[v])
            forbidden_twice |= forbidden_once & forbidden_by_v
            forbidden_once |= forbidden_by_v
    forbidden[u] = forbidden_once | (2**forbidden_twice.bit_length() - 1)
dfs(root, -1)

Now all that remains to prove the Lemma is to show that forbidden(u) is a monotone multivariate function as a function of forbidden(v_1) + b_{v_1}, ...,forbidden(v_m) + b_{v_m} over the children $$$v_1$$$,...,$$$v_m$$$ of $$$u$$$, as monotonicity would imply that the greedy labeling (picking all $$$b_v$$$'s to be $$$1$$$) minimizes forbidden(u). So we want to prove that the following multivariate function $$$f(x_1, ..., x_m)$$$ is monotone

def f(X):
    forbidden_once = forbidden_twice = 0
    for x in X:
        forbidden_twice |= forbidden_once & x
        forbidden_once |= x
    return forbidden_once | (2**forbidden_twice.bit_length() - 1)

I don't know of a simple argument to show this. However, one way to see that $$$f$$$ is monotone think of the input variables x_1, ..., x_m as being 0/1 vectors v_1, ..., v_m in a real vector space. Additionally, also think of $$$f(X) - 1$$$ as a 0/1 vector. In this view, $$$f(X) - 1$$$ is the lexographically smallest 0/1 vector $$$\geq v_1 + ... + v_m$$$. From this it is possible to draw the conclusion that $$$f$$$ must be monotone. If anyone has a cleaner argument for this, then please post it below.

Consider the following tree. Here I've picked the top node to be the root, and then I've greedily labeled the nodes from bottom to top.

In the following picture, I've drawn all of the different chains found in this tree (I've used one color per chain). There are five chains in total. Every node that has an ancestor with a higher label than its label, is part of the chain that starts at its lowest higher labeled ancestor. Each chain is then sorted in decreasing label order.

Using the chains above, we can easily build the shallowest decomposition tree of the original tree. In the following figure, showing the shallowest decomposition tree, I've kept the same colors as I used for the chains in the previous figure. As you can see, the edges in the decomposition tree have a 1-to-1 correspondence with the chain edges.

In the previous example, the root turned out to be the highest labeled node. But this is not always the case. In the following tree, the root (at the top) has label $$$0$$$, but the maximum label in the tree has label $$$3$$$.

Because the root doesn't have the highest label. On top of the chains going "downwards" (as in the previous example), there will also be a chain going upwards, consisting of the set of all nodes that are missing a higher labeled ancestor.

Finally this is the shallowest decomposition tree of the tree.

Each chain is a subset of nodes with distinct labels. A node $$$w$$$ is part of a chain starting at a node $$$u$$$, if $$$u \neq w$$$ and either

Case 1. $$$u$$$ is the lowest higher labeled ancestor of $$$w$$$.

Case 2. $$$u$$$ is the highest labeled node and $$$w$$$ is missing a higher labeled ancestor.

Furthermore, if two nodes share the same lowest higher labeled ancestor $$$u$$$ (Case 1). Then they are part of the same chain if and only if they are descendants of the same child $$$v$$$ of $$$u$$$. On the other hand, if two nodes are missing a higher labeled ancestor (Case 2), then they are always part of the same chain.

def ctz(x): # Count trailing zeros
    return (x & -x).bit_length() - 1

def shallowest_decomposition_tree(graph, root=0):
    n = len(graph)
  
    # Create a greedy labeling
    forbidden = [0] * n
    def dfs(u, p):
        forbidden_once = forbidden_twice = 0
        for v in graph[u]:
            if v != p:
                dfs(v, u)
                forbidden_by_v = forbidden[v] + 1
                forbidden_twice |= forbidden_once & forbidden_by_v
                forbidden_once |= forbidden_by_v
        forbidden[u] = forbidden_once | (2**forbidden_twice.bit_length() - 1)
    dfs(root, -1)
    labels = [ctz(forbidden[u] + 1) for u in range(n)]  
  
    # Extract the shallowest decomposition tree in O(n) time
    decomposition_tree = [[] for _ in range(n)]
    stacks = [[] for _ in range(max(labels) + 1)]
    def extract_chain(labels, u):
        # Extract a chain starting at node u
        while labels:
            label = labels.bit_length() - 1
            labels ^= 2**label
            v = stacks[label].pop()
            decomposition_tree[u].append(v)
            u = v
    def dfs(u, p):
        stacks[labels[u]].append(u)
        for v in graph[u]:
            if v != p: 
                dfs(v, u)
                extract_chain((forbidden[v] + 1) & (2**labels[u] - 1), u)
    dfs(root, -1)
    decomposition_root = stacks[-1].pop()
    extract_chain((forbidden[root] + 1) & (2**labels[decomposition_root] - 1), decomposition_root)
    return decomposition_tree, decomposition_root