Mo's Algorithm on Trees

Mo's algorithm adapted for tree path queries using Euler tour flattening and LCA via binary lifting.

[Range Queries]|

Jul 9, 2026

|explanatory_notes.md|

#mo-algorithm#tree#euler-tour#lca#offline

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 5;
const int LOG = 18;

vector<int> adj[MAXN];
int S[MAXN], E[MAXN], FT[2 * MAXN], dep[MAXN], anc[MAXN][LOG];
int nodeFreq[MAXN], n, q, timer = 1;
ll ans;
ll answers[MAXN];

void dfs(int u, int p) {
    S[u] = timer; FT[timer++] = u;
    for (int v : adj[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        anc[v][0] = u;
        for (int k = 1; k < LOG; k++)
            anc[v][k] = anc[anc[v][k-1]][k-1];
        dfs(v, u);
    }
    E[u] = timer; FT[timer++] = u;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = LOG - 1; k >= 0; k--)
        if (diff >> k & 1) u = anc[u][k];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (anc[u][k] != anc[v][k])
            u = anc[u][k], v = anc[v][k];
    return anc[u][0];
}

int64_t hilbert(int x, int y, int pw, int rot) {
    if (!pw) return 0;
    int hp = 1 << (pw - 1);
    int seg = (x < hp) ? ((y < hp) ? 0 : 3) : ((y < hp) ? 1 : 2);
    seg = (seg + rot) & 3;
    const int dr[] = {3, 0, 0, 1};
    int nx = x & (x ^ hp), ny = y & (y ^ hp);
    int64_t sub = int64_t(1) << (2 * pw - 2);
    int64_t add = hilbert(nx, ny, pw - 1, (rot + dr[seg]) & 3);
    return seg * sub + ((seg == 1 || seg == 2) ? add : sub - add - 1);
}

struct Query {
    int l, r, lc, idx;
    int64_t ord;
    bool operator<(const Query &o) const { return ord < o.ord; }
};

void add(int u) {
    // update ans when node u enters range
}

void rem(int u) {
    // update ans when node u leaves range
}

void toggle(int pos) {
    int u = FT[pos];
    nodeFreq[u] ^= 1;
    nodeFreq[u] ? add(u) : rem(u);
}

void solve() {
    dfs(1, 0);
    int pw = 1;
    while ((1 << pw) < 2 * n) pw++;

    vector<Query> qs(q);
    for (int i = 0; i < q; i++) {
        int u, v; cin >> u >> v;
        int l = lca(u, v);
        if (S[u] > S[v]) swap(u, v);
        if (l == u) qs[i] = {S[u] + 1, S[v], -1, i, hilbert(S[u] + 1, S[v], pw, 0)};
        else qs[i] = {E[u], S[v], l, i, hilbert(E[u], S[v], pw, 0)};
    }
    sort(qs.begin(), qs.end());

    int cl = qs[0].l, cr = qs[0].l - 1;
    for (auto &[l, r, lc, qi, _] : qs) {
        while (cl > l) toggle(--cl);
        while (cr < r) toggle(++cr);
        while (cl < l) toggle(cl++);
        while (cr > r) toggle(cr--);
        if (lc != -1) add(lc);
        answers[qi] = ans;
        if (lc != -1) rem(lc);
    }

    for (int i = 0; i < q; i++)
        cout << answers[i] << '\n';
}

99 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Mo's on Trees

Answers offline path queries on a tree by flattening the tree into a linear sequence via Euler tour, then applying Mo's algorithm on that sequence.

How It Works

Run DFS to compute entry time

S[u]

and exit time

E[u]

for each node. The flattened tour array FT[] maps positions to nodes — each node appears twice (entry and exit)

For a path query

(u, v)

where

\text{LCA}(u,v) = l

- If

l = u

: query range is

[S[u] + \text{VAL\_ON\_EDGE}, S[v]]

- Otherwise: query range is

[E[u], S[v]]

, and manually add/remove the LCA

A node appearing twice in the range cancels out (XOR toggle via nodeFreq), so only nodes on the actual path remain active

Queries sorted by Hilbert curve order for better cache performance

When to Use

Offline path queries on trees (distinct values on path, path sum, etc.)

Problems where add(node) and remove(node) are

O(1)

O(\log n)

When Heavy-Light Decomposition + segment tree feels overkill or doesn't fit the query type

Implementation

Fill in add(u) and remove(u) with problem-specific logic

Set VAL_ON_EDGE = true if values live on edges instead of nodes

Complexity

Time —

O((2n + q) \sqrt{q} \cdot f)

where

f

is cost of add/remove

Space —

O(n \log n)

for LCA table