Mo's Algorithm on Trees
Mo's algorithm on the bracket sequence
Ordinary Mo's algorithm only handles problems on a sequence, so we have to flatten the tree into one by force.
Take the bracket sequence of the tree, divide it into blocks, and run Mo's algorithm on it.
How exactly?
Procedure
Maintain the bracket sequence of the tree with a DFS: append \(x\) to the sequence on entering node \(x\), and append it again on leaving. The sequence has total length \(2N\).
Let \(st_x\) be the time at which \(x\) is entered and \(ed_x\) the time at which it is left.
By the properties of the bracket sequence, for a path \(u \to v\) in the tree (assume without loss of generality that \(st_u \le st_v\)):
- If \(\text{LCA}(u, v) = u\), every node on the path occurs exactly once in the range \([st_u, st_v]\), and every node off the path occurs 0 or 2 times.
- If \(\text{LCA}(u, v) \neq u\), every node on the path except \(\text{LCA}(u, v)\) occurs exactly once in the range \([ed_u, st_v]\), and every node off the path occurs 0 or 2 times. Handle \(\text{LCA}(u, v)\) separately: it occurs 0 times.
So while Mo's algorithm runs, it makes no difference whether the element a pointer passes records a node being pushed or popped: either way, the number of times that node occurs in the current range changes. We only need to maintain how many times each node \(x\) occurs. A node that occurs 0 or 2 times is not in the set of path nodes we maintain, and a node that occurs once is. So when the pointers of Mo's algorithm rest at \([st_u, st_v]\), the set is almost exactly the set of nodes on the path \(u \to v\).
In practice, maintain the number of occurrences of each node \(x\) modulo 2, which tells whether the node is present. Moving a pointer, whether it adds or deletes an element, then just flips the state of that node.
Note that for a query with \(\text{LCA} \neq u\), once the pointers are in place we have to add \(\text{LCA}(u, v)\) to the set temporarily by hand (flip its state), compute and record the answer to the query, and then remove \(\text{LCA}(u, v)\) from the set again (flip it once more), so that later pointer moves are not disturbed.
Example problems
Example: [WC2013] Candy Park
Problem statement: you are given a tree in which node \(i\) has color \(c_i\). Each query gives a path \(u_i\), \(v_i\) and asks for the value, over that path, of
\(\sum_{c}val_c\sum_{i=1}^{cnt_c}w_i\)
where \(val\) is the value of a color, \(cnt\) is the number of times the color occurs, and \(w\) is the value of the color once it has occurred \(i\) times.
Procedure
First turn the tree into a sequence. Each time a node is added, its contribution to the answer can be found in \(O(1)\): it is \(val_c\times w_{cnt_c+1}\).
But the range also sweeps the whole subtree of the starting point, which produces extra contributions. What can we do about that?
During the sweep, every node in the subtree of the starting point is swept twice, yet it should contribute 0.
So keep an array \(vis\), and every time node x is swept, XOR \(vis_x\) with 1.
If \(vis_x=0\), the contribution of this node is not counted.
The problem can therefore be solved with Mo's algorithm on trees.
To handle updates, just add a time dimension; this gives Mo's algorithm on trees with updates.
Finally, the range may not contain the LCA. When it does not, add the missing contribution, and we are done.
Implementation
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | |
True Mo's algorithm on trees
The method above merely turns the tree into a path. What follows is the real Mo's algorithm on trees.
Problems on Mo's algorithm are all template problems, so we do not explain the implementation in much detail.
Sorting the queries
Mo's algorithm is built on sqrt decomposition, so to guarantee the time complexity we need a way to divide a tree into blocks.
The conditions:
- Two nodes of the same block are no farther apart than the given block size.
- A block has neither too many nodes nor too few.
- Every node belongs to a block.
- Blocks with adjacent indices are not too far apart.
With these conditions in mind, look at the problem [SCOI2005] Royal Federation.
Starting from that problem, we only have to guarantee the last condition, and the question of how to form the blocks is settled.
Approach
Let lim be the desired block size. Run a DFS over the whole tree, and whenever the size of a subtree exceeds lim, put its nodes into one block. Some nodes may be left over at the root, so put those into the last block.
The method: maintain a stack as the current node, acting as the parent, visits its children. When the distance from the top of the stack to the parent exceeds the desired block size, pop those elements and make them one block. Whatever is left at the end forms a block of its own.
The final sort order: if the timestamp of the first endpoint is greater than that of the second, swap them; then sort with the block of the first endpoint as the first key and the timestamp of the second endpoint as the second key.
Moving the pointers
Procedure
A natural idea is to mark the nodes that are counted in the answer, let each pointer move straight to its target, and negate every node on the way.
But this has a problem. Suppose both pointers start at x, so x is marked. When the two pointers move to the same child (and in many other cases), x should end up unmarked, yet it stays marked: each pointer marks it once, and the two cancel out.
How do we fix this?
One property is obvious: such nodes are always LCAs, because only at an LCA can a mark be undone twice, which makes the undo fail.
So we never mark the LCA while moving. When a query needs its answer, we mark the LCA, and afterwards undo the mark.
Implementation
1 2 3 4 5 6 7 | |
To find the LCA we can use heavy-light decomposition. The block decomposition then fits into the first DFS of the heavy-light decomposition, and the DFS order of the second DFS can be used directly as the timestamps.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | |
Time complexity
This is the important part, because it decides the block size.
Let the block size be \(unit\):
- The x pointer: the nodes of a block are about \(unit\) apart, so within each block the x pointer moves \(unit^2\) times (\(unit\times dis_{\max}\)), for a total of \(n\times unit\) moves (\(unit^2 \times (\frac{n}{unit})\)).
- The y pointer: within each block it moves at most \(O(n)\) times, for a total of \(\frac{n^2}{unit}\) moves (\(n \times (\frac{n}{unit})\)).
The sum is smallest at about the square root (the blocks of Mo's algorithm on trees do not have a fixed size, so there is no need to follow this strictly).
Example: [WC2013] Candy Park
Because of the extra time dimension, a block size of around \(n^{0.6}\) is good enough.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | |
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: StudyingFather, Backl1ght, countercurrent-time, Ir1d, greyqz, MicDZ, ouuan, Linky, yinqf, 24OI-bot, Henry-ZHR, H-J-Granger, Chrogeek, Enter-tainer, yzxoi, Lookcatbox, ksyx, iamtwz, ImpleLee, Tiphereth-A, c-forrest, lailai0916, cute-yinqf (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.