guest@cp-base:~/home/range-queries$
templates/mos-on-trees.cpp
compilable
$cat templates/mos-on-trees

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
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
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
#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]S[u] and exit time E[u]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)(u, v) where LCA(u,v)=l\text{LCA}(u,v) = l:

    • - If l=ul = u: query range is [S[u]+VAL_ON_EDGE,S[v]][S[u] + \text{VAL\_ON\_EDGE}, S[v]]
    - Otherwise: query range is [E[u],S[v]][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(1) or O(log⁡n)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)q⋅f)O((2n + q) \sqrt{q} \cdot f) where ff is cost of add/remove

  • Space — O(nlog⁡n)O(n \log n) for LCA table