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 don't know 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 blazingly fast, both in C++ and Python etc...
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 store the following two things for every node in the tree:
deg[node] = The degree of the node.xor[node] = The XOR of all neighbours of node.
Storing this will only take $$$2 n$$$ integers, so it is very cheap memory wise. It is also very fast, because there are no .push_backs etc...
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.
This process ^ can easily be done with the following code ```py for node in range(n): while deg[node] == 1: nei = B[node]
