Hi Codeforces!

This is a blog about a really cool folklore technique that seems to have been forgotten over time. I currently only know of one place where it is mentioned on the internet, https://www.algonotes.com/en/minimal-memory-dp/ (from 2018), but I've been told that it is far older than this. I originally learnt of this technique a couple of years back when I was digging through the fastest submissions on 321-C - Ciel the Commander and I saw it being used in a submission 9076307 from 2014. I don't know if there is a name for this technique, so I've decided to call it XOR Linked Tree because of its close connection to XOR linked lists https://en.wikipedia.org/wiki/XOR_linked_list .

This is a technique for solving tree problems using very little time/memory. For example, every fastest solution in the "Tree Algorithms" section on https://cses.fi/problemset/ currently uses this technique. So it is record breaking fast!

The idea:

Suppose in the input of a problem, you are given a tree as $$$n - 1$$$ edges. To construct the XOR Linked Tree data-structure from this, you go through the list of edges and compute the following two things for every node in the tree:

1. deg[node] = The degree of the node.
2. xor[node] = The XOR of all neighbours of node.

Storing this will only take $$$2 n$$$ integers, so this is very cheap memory wise compared to an adjacency list. It is also really fast, since there are no expensive .push_back/.appends calls.

Claim: Using deg and xor, it is possible to reconstruct the tree.

Proof: Identify a leaf node in the tree (this can be done by finding a node with degree 1 in deg). Note that a leaf only has one neighbour, so the XOR of all of its neighbours is simply that neighbour. So the neighbour of a leaf is simply xor[leaf]. Now remove this leaf from the tree ("pluck it") by lowering the degree of its neighbour by one (deg[neighbour] -= 1) and XORing away leaf from xor[neighbour] (xor[neighbour] ^= leaf). Now we can just repeat this process of plucking leaves until there a single node left. We have now reconstructed the original tree.

Here is an implementation of the process described in the proof above ^

for node in range(n):
    while deg[node] == 1:
        nei = xor[node]

        # Pluck away node
        deg[node] = 0
        deg[nei] -= 1
        xor[nei] ^= node

        # Check if nei is now a leaf
        node = nei

Something to note is that it is possible to control which node is left at the end (the "root") by setting its degree to 0 before running the algorithm. So the final XOR Linked Tree traversal algorithm is

deg[root] = 0
for node in range(n):
    while deg[node] == 1:
        nei = xor[node]

        # Pluck away node
        deg[node] = 0
        deg[nei] -= 1
        xor[nei] ^= node

        # Check if nei is now a leaf
        node = nei

This is it! This is the entire algorithm! The deg list is now completely 0 and the xor list now contains the parent of every node.

Discussion

This tree traversal algorithm is different than DFS or BFS. For one, it doesn't use anything like a queue or a stack. Instead it simply removes one leaf using a while loop inside of a for loop. The order you traverse the nodes in is kind of like doing a BFS in reverse, but it is not exactly the same thing.

Discussion (Advanced)

One last thing I want to mention is that on some tree problems, you need specifically need a DFS ordering. For example, there are tree problems on cses.fi that requires you to compute LCA. Most (if not all) algorithms/data-structures for computing LCA is based on DFS. Is it still possible to use XOR Linked Tree traversal algorithm for those problems?

The answer is yes. It is possible to use the XOR Linked Tree traversal algorithm to compute a DFS ordering. The trick is first compute subtree sizes, and then use this information to compute where in a DFS ordering each node should be.

# Store the order of the plucked nodes in the XOR Linked Tree traversal
XOR_traversal_order = []

deg[root] = 0
for node in range(n):
    while deg[node] == 1:
        nei = xor[node]

        # Pluck away node
        XOR_traversal_order.append(node)
        deg[node] = 0
        deg[nei] -= 1
        xor[nei] ^= node

        # Check if nei is now a leaf
        node = nei

# Compute subtree sizes
subtree_size = [1] * n
for node in XOR_traversal_order:
    # Note that xor[node] is the parent of node
    p = xor[node]
    subtree_size[p] += subtree_size[node]

# Compute the index each node would have in a DFS using subtree_size
# NOTE: This modifies subtree_size
for node in reversed(XOR_traversal_order):
    p = xor[node]
    subtree_size[node], subtree_size[p] = subtree_size[p], subtree_size[p] - subtree_size[node]

DFS_traversal_order = [None] * n
for node in range(n):
    DFS_traversal_order[subtree_size[node] - 1] = node

This might be one of the weirdest ways to do a DFS ever. But it is blazingly fast!