Mo's Algorithm on Trees

Extend Mo’s algorithm to path queries on a tree by flattening the tree into a sequence where every path corresponds to a contiguous range.

The Euler tour with two occurrences

Record each vertex twice — on entry (tin[v]) and on exit (tout[v]) — giving an array of length $2n$.

int timer_ = 0;
vector<int> euler(2 * n), tin(n), tout(n);
void dfs(int v, int p) {
    tin[v] = timer_; euler[timer_++] = v;
    for (int u : adj[v]) if (u != p) dfs(u, v);
    tout[v] = timer_; euler[timer_++] = v;
}

Mapping a path to a range

For a query on the path $u\to v$ (assume $\mathrm{tin}[u]\le \mathrm{tin}[v]$), let $l=\mathrm{LCA}(u,v)$:

Case	Range	Extra
$l=u$ ($u$ is an ancestor of $v$)	$[\mathrm{tin}[u],\mathrm{tin}[v]]$	—
otherwise	$[\mathrm{tout}[u],\mathrm{tin}[v]]$	add the LCA separately

The key rule: a vertex whose occurrences both lie inside the range is not on the path (it is in a side subtree that the path enters and leaves); a vertex appearing exactly once is on the path.

So the add/remove operation toggles:

vector<int> cnt(n, 0);
void toggle(int v) {
    if (cnt[v]) { cnt[v] = 0; removeVertex(v); }
    else        { cnt[v] = 1; addVertex(v); }
}

Each add/remove in the Mo loop becomes a toggle, and the parity handles the “appears twice” case automatically.

The full loop

sort(queries.begin(), queries.end(), moComparator);      // by block of L, then R
int curL = 0, curR = -1;
for (auto& q : queries) {
    while (curR < q.r) toggle(euler[++curR]);
    while (curL > q.l) toggle(euler[--curL]);
    while (curR > q.r) toggle(euler[curR--]);
    while (curL < q.l) toggle(euler[curL++]);
    if (q.lca != -1) toggle(q.lca);                       // include the LCA
    ans[q.id] = currentAnswer;
    if (q.lca != -1) toggle(q.lca);                       // and remove it again
}

Complexity: $O((n+q)\sqrt{n})$ — the array has length $2n$, so the constant is doubled relative to array Mo’s.

What it answers

Anything that Mo’s answers on an array, but along a tree path:

Query	State
Number of distinct values on the path	a frequency array + a distinct counter
Most frequent value on the path	frequency + count-of-counts
Number of pairs with equal values	maintain the pair count incrementally
Sum of $f({\text{count}}_v)$ over values	incremental
$k$-th smallest on the path	Mo’s + a value BIT, $O(n\sqrt{n}\log n)$

Subtree queries are easier

For subtree (not path) queries, use the ordinary Euler tour with tin/tout — the subtree is a contiguous range and plain array Mo’s applies directly, with no toggling and no LCA correction.

Better still: subtree queries usually have an $O(n\log n)$ solution via DSU on tree or a BIT over the Euler tour. Reach for Mo’s only when the aggregate resists both.

Alternatives for path queries

Situation	Method	Cost
Aggregate is associative, no updates	binary lifting	$O(\log n)$
Aggregate is associative, with updates	HLD + segment tree	$O({\log }^{2}n)$
Aggregate needs add/remove semantics	Mo’s on trees	$O(n\sqrt{n})$
Counting over all paths	centroid decomposition	$O(n\log n)$
Small vertex subsets per query	virtual tree	$O(k\log n)$

Mo’s on trees is the fallback for aggregates like “number of distinct values” that HLD cannot merge — its niche is real but narrow.

Practical notes

• Precompute the LCA with binary lifting or Euler+sparse table.
• Use the Hilbert curve ordering of queries (as in array Mo’s) for a ~30% constant-factor improvement.
• Watch the memory: the Euler array is $2n$, and the frequency array is over the value range (compress it).

See also: Mo’s Algorithm · Euler Tour · DSU on Tree