树上莫队

What · 是什么

树上莫队（Mo's algorithm on trees）把树上的路径询问（如路径上不同颜色数、路径上某个值的出现次数）转化为序列区间询问，再用普通莫队求解。做法：DFS 生成括号序（进入节点 x 时记 st[x]、离开时记 ed[x]，序列长 2n），对任意路径 u→v（设 st[u]≤st[v]）：若 LCA(u,v)=u 则路径节点恰好在区间 [st[u], st[v]] 中出现一次；否则路径上除 LCA 外的节点在区间 [ed[u], st[v]] 中出现一次，LCA 需在回答时临时加入。莫队指针移动时对每个节点翻转出现状态（异或 1），状态为 1 的节点构成当前路径集合。

Why · 为什么

How · 实现

伪代码

dfs(1): st[x]=len(euler); euler.append(x); for child: dfs; ed[x]=len(euler); euler.append(x)
preprocess LCA (倍增)
for (u,v,id) in queries:
    if st[u] > st[v]: swap
    w = lca(u,v)
    if w == u: conv = (st[u], st[v], -1)
    else:      conv = (ed[u], st[v], w)
sort by (l//block, r 奇偶化)
while moving pointers: toggle(euler[pos])
toggle(x): vis[x] ^= 1; if vis[x]: add col[x] else remove col[x]
answer: if w!=-1: toggle(w); ans[id]=cur; toggle(w)

Python 实现

def mo_on_tree(n, adj, col, queries):
    """树上莫队（括号序）：路径 u-v 上不同颜色的数量.
    adj: 邻接表 0-indexed; col: 各节点颜色; queries: [(u,v,id)].
    返回按 id 的答案列表."""
    import math, sys
    sys.setrecursionlimit(1 << 20)
    st = [0] * n; ed = [0] * n
    euler = []
    dep = [0] * n
    parent = [-1] * n
    def dfs(u, p):
        parent[u] = p
        st[u] = len(euler); euler.append(u)
        for w in adj[u]:
            if w != p:
                dep[w] = dep[u] + 1
                dfs(w, u)
        ed[u] = len(euler); euler.append(u)
    dfs(0, -1)
    # LCA 用倍增
    LOG = (n + 1).bit_length()
    up = [[-1] * n for _ in range(LOG)]
    up[0] = parent[:]
    for k in range(1, LOG):
        for v in range(n):
            mid = up[k-1][v]
            up[k][v] = up[k-1][mid] if mid != -1 else -1
    def lca(u, v):
        if dep[u] < dep[v]:
            u, v = v, u
        diff = dep[u] - dep[v]
        for k in range(LOG):
            if diff >> k & 1:
                u = up[k][u]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u = up[k][u]; v = up[k][v]
        return parent[u]
    m2 = len(euler)
    block = max(1, int(math.sqrt(m2)))
    def conv(u, v):
        if st[u] > st[v]:
            u, v = v, u
        w = lca(u, v)
        if w == u:
            return (st[u], st[v], -1)
        return (ed[u], st[v], w)
    converted = []
    for u, v, idx in queries:
        l, r, w = conv(u, v)
        converted.append((l, r, w, idx))
    converted.sort(key=lambda q: (q[0] // block, q[1] if (q[0] // block) % 2 == 0 else -q[1]))
    vis = [0] * n            # 当前在集合中的次数
    cnt = [0] * (max(col) + 1)
    cur = 0
    def toggle(x):
        nonlocal cur
        if vis[x]:
            vis[x] = 0
            cnt[col[x]] -= 1
            if cnt[col[x]] == 0:
                cur -= 1
        else:
            vis[x] = 1
            if cnt[col[x]] == 0:
                cur += 1
            cnt[col[x]] += 1
    ans = [0] * len(queries)
    l = 0; r = -1
    for ql, qr, w, idx in converted:
        while l > ql:
            l -= 1; toggle(euler[l])
        while r < qr:
            r += 1; toggle(euler[r])
        while l < ql:
            toggle(euler[l]); l += 1
        while r > qr:
            toggle(euler[r]); r -= 1
        if w != -1:
            toggle(w)
        ans[idx] = cur
        if w != -1:
            toggle(w)
    return ans

if __name__ == "__main__":
    # 树: 0-1, 0-2, 1-3; 颜色 [1,2,2,3]
    n = 4
    adj = [[1, 2], [0, 3], [0], [1]]
    col = [1, 2, 2, 3]
    queries = [(0, 3, 0), (2, 3, 1), (1, 1, 2)]
    res = mo_on_tree(n, adj, col, queries)
    # 路径 0-3: 0,1,3 -> 颜色 {1,2,3}=3; 2-3: 2,0,1,3 -> {1,2,3}=3; 1-1: {2}=1
    assert res == [3, 3, 1], res
    # 随机交叉验证（小树暴力 BFS 路径）
    import random
    def brute(n, adj, col, u, v):
        # BFS 找路径
        from collections import deque
        par = [-1] * n
        par[u] = u
        q = deque([u])
        while q:
            x = q.popleft()
            if x == v:
                break
            for w in adj[x]:
                if par[w] == -1:
                    par[w] = x
                    q.append(w)
        path = []
        x = v
        while True:
            path.append(x)
            if x == u:
                break
            x = par[x]
        return len(set(col[i] for i in path))
    random.seed(17)
    for _ in range(100):
        n = random.randint(1, 8)
        adj = [[] for _ in range(n)]
        for i in range(1, n):
            p = random.randrange(i)
            adj[i].append(p); adj[p].append(i)
        col = [random.randint(1, 4) for _ in range(n)]
        for _q in range(20):
            u = random.randrange(n); v = random.randrange(n)
            got = mo_on_tree(n, adj, col, [(u, v, 0)])[0]
            exp = brute(n, adj, col, u, v)
            assert got == exp, (n, adj, col, u, v, got, exp)
    print("mo_on_tree OK")

易错点

• LCA 不在区间内的询问，必须临时 toggle(LCA) 记录答案后再 toggle 回来，否则答案少/多一个节点
• 括号序区间是 ed[u]..st[v]（LCA≠u 时），不要误用 st[u]..st[v]（会把 u 的子树整个算进去）
• toggle 状态维护的是出现次数奇偶，不是「是否加入」布尔——同一节点被指针扫过两次会抵消
• 块长按 2n（括号序长度）计算，不是按 n
• 深树递归 DFS 会爆栈，需 sys.setrecursionlimit 或迭代实现

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/misc/mo-algo-on-tree.md
• OI Wiki✓ https://oi-wiki.org/misc/mo-algo-on-tree/
• uoj✓ https://uoj.ac/problem/58